/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / web / planar.tex

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 5c 69 6e 70 75 74 20 63 | 77 65 62 6d 61 63 0a 5c |\input c|webmac.\|
|00000010| 64 6f 63 75 6d 65 6e 74 | 73 74 79 6c 65 5b 63 6f |document|style[co|
|00000020| 6d 6d 65 6e 74 73 2c 61 | 34 2c 70 73 66 69 67 5d |mments,a|4,psfig]|
|00000030| 7b 63 77 65 62 7d 0a 0a | 5c 69 6e 70 75 74 7b 2f |{cweb}..|\input{/|
|00000040| 4b 4d 2f 75 73 72 2f 73 | 63 68 69 72 72 61 2f 73 |KM/usr/s|chirra/s|
|00000050| 74 79 6c 65 73 2f 74 72 | 61 6e 73 66 69 67 7d 0a |tyles/tr|ansfig}.|
|00000060| 0a 5c 76 6f 66 66 73 65 | 74 3d 2d 30 2e 35 63 6d |.\voffse|t=-0.5cm|
|00000070| 0a 5c 74 65 78 74 77 69 | 64 74 68 09 09 31 34 63 |.\textwi|dth..14c|
|00000080| 6d 0a 5c 6f 64 64 73 69 | 64 65 6d 61 72 67 69 6e |m.\oddsi|demargin|
|00000090| 20 20 20 20 20 20 20 20 | 20 20 30 2e 34 63 6d 0a |        |  0.4cm.|
|000000a0| 5c 65 76 65 6e 73 69 64 | 65 6d 61 72 67 69 6e 20 |\evensid|emargin |
|000000b0| 20 20 20 20 20 20 20 20 | 31 2e 34 63 6d 0a 5c 6d |        |1.4cm.\m|
|000000c0| 61 72 67 69 6e 70 61 72 | 77 69 64 74 68 09 09 31 |arginpar|width..1|
|000000d0| 2e 39 63 6d 0a 5c 6d 61 | 72 67 69 6e 70 61 72 73 |.9cm.\ma|rginpars|
|000000e0| 65 70 09 09 30 2e 34 63 | 6d 0a 5c 6d 61 72 67 69 |ep..0.4c|m.\margi|
|000000f0| 6e 70 61 72 70 75 73 68 | 09 09 30 2e 34 63 6d 0a |nparpush|..0.4cm.|
|00000100| 5c 74 6f 70 6d 61 72 67 | 69 6e 09 09 30 63 6d 0a |\topmarg|in..0cm.|
|00000110| 5c 68 65 61 64 73 65 70 | 09 09 31 2e 35 63 6d 0a |\headsep|..1.5cm.|
|00000120| 5c 74 65 78 74 68 65 69 | 67 68 74 09 09 32 31 2e |\texthei|ght..21.|
|00000130| 35 63 6d 0a 5c 66 6f 6f | 74 73 6b 69 70 09 09 32 |5cm.\foo|tskip..2|
|00000140| 2e 32 63 6d 0a 0a 0a 0a | 5c 62 65 67 69 6e 7b 64 |.2cm....|\begin{d|
|00000150| 6f 63 75 6d 65 6e 74 7d | 0a 0a 0a 0a 5c 74 68 69 |ocument}|....\thi|
|00000160| 73 70 61 67 65 73 74 79 | 6c 65 7b 65 6d 70 74 79 |spagesty|le{empty|
|00000170| 7d 0a 0a 5c 72 65 6e 65 | 77 63 6f 6d 6d 61 6e 64 |}..\rene|wcommand|
|00000180| 7b 5c 74 68 65 66 6f 6f | 74 6e 6f 74 65 7d 7b 5c |{\thefoo|tnote}{\|
|00000190| 66 6e 73 79 6d 62 6f 6c | 7b 66 6f 6f 74 6e 6f 74 |fnsymbol|{footnot|
|000001a0| 65 7d 7d 0a 0a 20 20 20 | 20 20 20 20 20 5c 74 69 |e}}..   |     \ti|
|000001b0| 74 6c 65 7b 41 6e 20 49 | 6d 70 6c 65 6d 65 6e 74 |tle{An I|mplement|
|000001c0| 61 74 69 6f 6e 20 6f 66 | 20 74 68 65 5c 5c 0a 20 |ation of| the\\. |
|000001d0| 48 6f 70 63 72 6f 66 74 | 20 61 6e 64 20 54 61 72 |Hopcroft| and Tar|
|000001e0| 6a 61 6e 5c 5c 0a 20 50 | 6c 61 6e 61 72 69 74 79 |jan\\. P|lanarity|
|000001f0| 20 54 65 73 74 20 61 6e | 64 20 45 6d 62 65 64 64 | Test an|d Embedd|
|00000200| 69 6e 67 20 41 6c 67 6f | 72 69 74 68 6d 7d 5c 74 |ing Algo|rithm}\t|
|00000210| 68 61 6e 6b 73 7b 54 68 | 69 73 20 77 6f 72 6b 20 |hanks{Th|is work |
|00000220| 77 61 73 20 73 75 70 70 | 6f 72 74 65 64 20 69 6e |was supp|orted in|
|00000230| 20 70 61 72 74 0a 62 79 | 20 74 68 65 20 47 65 72 | part.by| the Ger|
|00000240| 6d 61 6e 20 4d 69 6e 69 | 73 0a 74 72 79 20 66 6f |man Mini|s.try fo|
|00000250| 72 20 52 65 73 65 61 72 | 63 68 20 61 6e 64 20 54 |r Resear|ch and T|
|00000260| 65 63 68 6e 6f 6c 6f 67 | 79 20 28 42 75 6e 64 65 |echnolog|y (Bunde|
|00000270| 73 6d 69 6e 69 73 74 65 | 72 69 75 6d 20 66 5c 22 |sministe|rium f\"|
|00000280| 75 72 20 46 6f 72 73 63 | 68 75 6e 67 20 75 6e 64 |ur Forsc|hung und|
|00000290| 0a 54 65 63 68 6e 6f 6c | 6f 67 69 65 29 20 75 6e |.Technol|ogie) un|
|000002a0| 64 65 72 20 67 72 61 6e | 74 20 49 54 53 0a 20 39 |der gran|t ITS. 9|
|000002b0| 31 30 33 20 61 6e 64 20 | 62 79 20 74 68 65 20 45 |103 and |by the E|
|000002c0| 53 50 52 49 54 20 42 61 | 73 69 63 20 52 65 73 65 |SPRIT Ba|sic Rese|
|000002d0| 61 72 63 68 20 41 63 74 | 69 6f 6e 73 20 50 72 6f |arch Act|ions Pro|
|000002e0| 67 72 61 6d 20 75 6e 64 | 65 72 20 63 6f 6e 74 72 |gram und|er contr|
|000002f0| 61 63 74 20 4e 6f 2e 20 | 37 31 34 31 0a 28 70 72 |act No. |7141.(pr|
|00000300| 6f 6a 65 63 74 20 41 4c | 43 4f 4d 20 49 49 29 2e |oject AL|COM II).|
|00000310| 7d 0a 0a 5c 61 75 74 68 | 6f 72 7b 4b 75 72 74 20 |}..\auth|or{Kurt |
|00000320| 4d 65 68 6c 68 6f 72 6e | 5c 5c 0a 20 20 20 20 20 |Mehlhorn|\\.     |
|00000330| 20 20 20 7b 5c 66 6f 6f | 74 6e 6f 74 65 73 69 7a |   {\foo|tnotesiz|
|00000340| 65 20 20 4d 61 78 2d 50 | 6c 61 6e 63 6b 2d 49 6e |e  Max-P|lanck-In|
|00000350| 73 74 69 74 75 74 20 66 | 5c 22 75 72 20 49 6e 66 |stitut f|\"ur Inf|
|00000360| 6f 72 6d 61 74 69 6b 2c | 7d 5c 5c 5b 2d 30 2e 37 |ormatik,|}\\[-0.7|
|00000370| 65 78 5d 0a 20 20 20 09 | 7b 5c 66 6f 6f 74 6e 6f |ex].   .|{\footno|
|00000380| 74 65 73 69 7a 65 20 36 | 36 31 32 33 20 53 61 61 |tesize 6|6123 Saa|
|00000390| 72 62 72 5c 22 75 63 6b | 65 6e 2c 20 47 65 72 6d |rbr\"uck|en, Germ|
|000003a0| 61 6e 79 7d 5c 5c 5b 30 | 2e 37 65 78 5d 0a 09 5c |any}\\[0|.7ex]..\|
|000003b0| 61 6e 64 20 50 65 74 72 | 61 20 4d 75 74 7a 65 6c |and Petr|a Mutzel|
|000003c0| 5c 5c 0a 20 20 20 20 20 | 20 20 20 7b 5c 66 6f 6f |\\.     |   {\foo|
|000003d0| 74 6e 6f 74 65 73 69 7a | 65 20 20 49 6e 73 74 69 |tnotesiz|e  Insti|
|000003e0| 74 75 74 20 66 5c 22 75 | 72 20 49 6e 66 6f 72 6d |tut f\"u|r Inform|
|000003f0| 61 74 69 6b 2c 7d 5c 5c | 5b 2d 30 2e 37 65 78 5d |atik,}\\|[-0.7ex]|
|00000400| 0a 09 7b 66 6f 6f 74 6e | 6f 74 65 73 69 7a 65 20 |..{footn|otesize |
|00000410| 55 6e 69 76 65 72 73 69 | 74 5c 22 61 74 20 7a 75 |Universi|t\"at zu|
|00000420| 20 4b 5c 22 6f 6c 6e 2c | 20 35 30 39 36 39 20 4b | K\"oln,| 50969 K|
|00000430| 5c 22 6f 6c 6e 7d 5c 5c | 5b 30 2e 37 65 78 5d 0a |\"oln}\\|[0.7ex].|
|00000440| 09 5c 61 6e 64 20 53 74 | 65 66 61 6e 20 4e 5c 22 |.\and St|efan N\"|
|00000450| 61 68 65 72 5c 5c 0a 20 | 20 20 20 20 20 20 20 7b |aher\\. |       {|
|00000460| 5c 66 6f 6f 74 6e 6f 74 | 65 73 69 7a 65 20 20 4d |\footnot|esize  M|
|00000470| 61 78 2d 50 6c 61 6e 63 | 6b 2d 49 6e 73 74 69 74 |ax-Planc|k-Instit|
|00000480| 75 74 20 66 5c 22 75 72 | 20 49 6e 66 6f 72 6d 61 |ut f\"ur| Informa|
|00000490| 74 69 6b 2c 7d 5c 5c 5b | 2d 30 2e 37 65 78 5d 0a |tik,}\\[|-0.7ex].|
|000004a0| 20 20 20 09 7b 5c 66 6f | 6f 74 6e 6f 74 65 73 69 |   .{\fo|otnotesi|
|000004b0| 7a 65 20 36 36 31 32 33 | 20 53 61 61 72 62 72 5c |ze 66123| Saarbr\|
|000004c0| 22 75 63 6b 65 6e 2c 20 | 47 65 72 6d 61 6e 79 7d |"ucken, |Germany}|
|000004d0| 5c 5c 5b 30 2e 37 65 78 | 5d 7d 0a 0a 0a 20 20 20 |\\[0.7ex|]}...   |
|000004e0| 20 20 20 20 20 5c 64 61 | 74 65 7b 7d 0a 20 20 20 |     \da|te{}.   |
|000004f0| 20 20 20 20 20 5c 6d 61 | 6b 65 74 69 74 6c 65 0a |     \ma|ketitle.|
|00000500| 0a 0a 5c 73 65 74 63 6f | 75 6e 74 65 72 7b 70 61 |..\setco|unter{pa|
|00000510| 67 65 7d 7b 30 7d 0a 5c | 74 68 69 73 70 61 67 65 |ge}{0}.\|thispage|
|00000520| 73 74 79 6c 65 7b 65 6d | 70 74 79 7d 0a 0a 25 25 |style{em|pty}..%%|
|00000530| 25 25 25 25 25 20 41 62 | 73 74 72 61 63 74 20 25 |%%%%% Ab|stract %|
|00000540| 25 25 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |%%%%%%%%|%%%%%%%%|
|00000550| 25 25 25 25 25 25 25 25 | 25 25 25 25 25 25 0a 0a |%%%%%%%%|%%%%%%..|
|00000560| 5c 76 73 70 61 63 65 2a | 7b 32 2e 32 63 6d 7d 0a |\vspace*|{2.2cm}.|
|00000570| 0a 5c 62 65 67 69 6e 7b | 61 62 73 74 72 61 63 74 |.\begin{|abstract|
|00000580| 7d 0a 57 65 20 64 65 73 | 63 72 69 62 65 20 61 6e |}.We des|cribe an|
|00000590| 20 69 6d 70 6c 65 6d 65 | 6e 74 61 74 69 6f 6e 20 | impleme|ntation |
|000005a0| 6f 66 20 74 68 65 20 48 | 6f 70 63 72 6f 66 74 20 |of the H|opcroft |
|000005b0| 61 6e 64 20 54 61 72 6a | 61 6e 20 70 6c 61 6e 61 |and Tarj|an plana|
|000005c0| 72 69 74 79 20 74 65 73 | 74 20 61 6e 64 0a 65 6d |rity tes|t and.em|
|000005d0| 62 65 64 64 69 6e 67 20 | 61 6c 67 6f 72 69 74 68 |bedding |algorith|
|000005e0| 6d 2e 20 54 68 65 20 70 | 72 6f 67 72 61 6d 20 74 |m. The p|rogram t|
|000005f0| 65 73 74 73 20 74 68 65 | 20 70 6c 61 6e 61 72 69 |ests the| planari|
|00000600| 74 79 20 6f 66 20 74 68 | 65 20 69 6e 70 75 74 0a |ty of th|e input.|
|00000610| 67 72 61 70 68 20 61 6e | 64 20 65 69 74 68 65 72 |graph an|d either|
|00000620| 20 63 6f 6e 73 74 72 75 | 63 74 73 20 61 20 63 6f | constru|cts a co|
|00000630| 6d 62 69 6e 61 74 6f 72 | 69 61 6c 20 65 6d 62 65 |mbinator|ial embe|
|00000640| 64 64 69 6e 67 20 28 69 | 66 20 74 68 65 20 67 72 |dding (i|f the gr|
|00000650| 61 70 68 0a 69 73 20 70 | 6c 61 6e 61 72 29 20 6f |aph.is p|lanar) o|
|00000660| 72 20 65 78 68 69 62 69 | 74 73 20 61 20 4b 75 72 |r exhibi|ts a Kur|
|00000670| 61 74 6f 77 73 6b 69 20 | 73 75 62 67 72 61 70 68 |atowski |subgraph|
|00000680| 20 28 69 66 20 74 68 65 | 20 67 72 61 70 68 20 69 | (if the| graph i|
|00000690| 73 20 6e 6f 6e 2d 70 6c | 61 6e 61 72 29 2e 0a 0a |s non-pl|anar)...|
|000006a0| 5c 65 6e 64 7b 61 62 73 | 74 72 61 63 74 7d 0a 0a |\end{abs|tract}..|
|000006b0| 5c 74 61 62 6c 65 6f 66 | 63 6f 6e 74 65 6e 74 73 |\tableof|contents|
|000006c0| 0a 0a 0a 5c 4e 7b 31 7d | 7b 31 7d 49 6e 74 72 6f |...\N{1}|{1}Intro|
|000006d0| 64 75 63 74 69 6f 6e 2e | 0a 0a 57 65 20 64 65 73 |duction.|..We des|
|000006e0| 63 69 62 65 20 74 77 6f | 20 70 72 6f 63 65 64 75 |cibe two| procedu|
|000006f0| 72 65 73 20 74 6f 20 74 | 65 73 74 20 74 68 65 20 |res to t|est the |
|00000700| 70 6c 61 6e 61 72 69 74 | 79 20 6f 66 20 61 20 67 |planarit|y of a g|
|00000710| 72 61 70 68 20 5c 50 42 | 7b 5c 7c 47 7d 3a 0a 0a |raph \PB|{\|G}:..|
|00000720| 5c 62 65 67 69 6e 7b 63 | 65 6e 74 65 72 7d 0a 5c |\begin{c|enter}.\|
|00000730| 50 42 7b 5c 26 7b 62 6f | 6f 6c 7d 20 5c 5c 7b 70 |PB{\&{bo|ol} \\{p|
|00000740| 6c 61 6e 61 72 7d 28 5c | 26 7b 67 72 61 70 68 7d |lanar}(\|&{graph}|
|00000750| 20 24 7b 7d 7b 5c 41 4e | 44 7d 5c 7c 47 2c 7b 7d | ${}{\AN|D}\|G,{}|
|00000760| 24 5c 26 7b 62 6f 6f 6c | 7d 20 5c 5c 7b 65 6d 62 |$\&{bool|} \\{emb|
|00000770| 65 64 7d 24 7b 7d 5c 4b | 25 0a 5c 5c 7b 66 61 6c |ed}${}\K|%.\\{fal|
|00000780| 73 65 7d 29 24 7d 0a 5c | 65 6e 64 7b 63 65 6e 74 |se})$}.\|end{cent|
|00000790| 65 72 7d 0a 0a 61 6e 64 | 0a 0a 5c 62 65 67 69 6e |er}..and|..\begin|
|000007a0| 7b 63 65 6e 74 65 72 7d | 0a 5c 50 42 7b 5c 26 7b |{center}|.\PB{\&{|
|000007b0| 62 6f 6f 6c 7d 20 5c 5c | 7b 70 6c 61 6e 61 72 7d |bool} \\|{planar}|
|000007c0| 28 5c 26 7b 67 72 61 70 | 68 7d 20 24 7b 7d 7b 5c |(\&{grap|h} ${}{\|
|000007d0| 41 4e 44 7d 5c 7c 47 2c | 5c 26 7b 6c 69 73 74 7d |AND}\|G,|\&{list}|
|000007e0| 5c 6c 61 6e 67 6c 65 5c | 26 7b 65 64 67 65 7d 25 |\langle\|&{edge}%|
|000007f0| 0a 5c 72 61 6e 67 6c 65 | 7b 7d 24 20 24 7b 7d 7b |.\rangle|{}$ ${}{|
|00000800| 5c 41 4e 44 7d 5c 7c 50 | 2c 7b 7d 24 5c 26 7b 62 |\AND}\|P|,{}$\&{b|
|00000810| 6f 6f 6c 7d 20 5c 5c 7b | 65 6d 62 65 64 7d 24 7b |ool} \\{|embed}${|
|00000820| 7d 5c 4b 5c 5c 7b 66 61 | 6c 73 65 7d 29 24 7d 2e |}\K\\{fa|lse})$}.|
|00000830| 0a 5c 65 6e 64 7b 63 65 | 6e 74 65 72 7d 0a 0a 42 |.\end{ce|nter}..B|
|00000840| 6f 74 68 20 74 61 6b 65 | 20 61 20 64 69 72 65 63 |oth take| a direc|
|00000850| 74 65 64 20 67 72 61 70 | 68 20 5c 50 42 7b 5c 7c |ted grap|h \PB{\||
|00000860| 47 7d 20 61 6e 64 20 74 | 65 73 74 20 69 74 20 66 |G} and t|est it f|
|00000870| 6f 72 20 70 6c 61 6e 61 | 72 69 74 79 2e 0a 49 66 |or plana|rity..If|
|00000880| 20 74 68 65 20 67 72 61 | 70 68 20 69 73 20 70 6c | the gra|ph is pl|
|00000890| 61 6e 61 72 20 61 6e 64 | 20 62 69 64 69 72 65 63 |anar and| bidirec|
|000008a0| 74 65 64 2c 20 69 2e 65 | 2e 2c 20 66 6f 72 20 65 |ted, i.e|., for e|
|000008b0| 76 65 72 79 20 65 64 67 | 65 20 6f 66 20 5c 50 42 |very edg|e of \PB|
|000008c0| 7b 5c 7c 47 7d 20 69 74 | 73 0a 72 65 76 65 72 73 |{\|G} it|s.revers|
|000008d0| 61 6c 20 69 73 20 61 6c | 73 6f 20 69 6e 20 5c 50 |al is al|so in \P|
|000008e0| 42 7b 5c 7c 47 7d 2c 20 | 61 6e 64 20 74 68 65 20 |B{\|G}, |and the |
|000008f0| 61 72 67 75 6d 65 6e 74 | 20 5c 50 42 7b 5c 5c 7b |argument| \PB{\\{|
|00000900| 65 6d 62 65 64 7d 7d 20 | 69 73 20 74 72 75 65 2c |embed}} |is true,|
|00000910| 20 74 68 65 6e 0a 74 68 | 65 79 0a 61 6c 73 6f 20 | then.th|ey.also |
|00000920| 63 6f 6d 70 75 74 65 20 | 61 20 63 6f 6d 62 69 6e |compute |a combin|
|00000930| 61 74 6f 72 69 61 6c 20 | 65 6d 62 65 64 64 69 6e |atorial |embeddin|
|00000940| 67 20 6f 66 20 5c 50 42 | 7b 5c 7c 47 7d 20 28 62 |g of \PB|{\|G} (b|
|00000950| 79 20 73 75 69 74 61 62 | 6c 79 20 72 65 6f 72 64 |y suitab|ly reord|
|00000960| 65 72 69 6e 67 0a 69 74 | 73 20 61 64 6a 61 63 65 |ering.it|s adjace|
|00000970| 6e 63 79 20 6c 69 73 74 | 73 29 2e 20 49 66 20 74 |ncy list|s). If t|
|00000980| 68 65 20 67 72 61 70 68 | 20 5c 50 42 7b 5c 7c 47 |he graph| \PB{\|G|
|00000990| 7d 20 69 73 0a 6e 6f 6e | 2d 70 6c 61 6e 61 72 20 |} is.non|-planar |
|000009a0| 74 68 65 6e 20 74 68 65 | 20 66 69 72 73 74 20 76 |then the| first v|
|000009b0| 65 72 73 69 6f 6e 20 6f | 66 20 5c 50 42 7b 5c 5c |ersion o|f \PB{\\|
|000009c0| 7b 70 6c 61 6e 61 72 7d | 7d 20 6f 6e 6c 79 20 72 |{planar}|} only r|
|000009d0| 65 63 6f 72 64 73 20 74 | 68 61 74 20 66 61 63 74 |ecords t|hat fact|
|000009e0| 2e 0a 54 68 65 20 73 65 | 63 6f 6e 64 20 76 65 72 |..The se|cond ver|
|000009f0| 73 69 6f 6e 20 69 6e 20 | 61 64 64 69 74 69 6f 6e |sion in |addition|
|00000a00| 20 72 65 74 75 72 6e 73 | 20 61 20 73 75 62 67 72 | returns| a subgr|
|00000a10| 61 70 68 20 6f 66 20 5c | 50 42 7b 5c 7c 47 7d 20 |aph of \|PB{\|G} |
|00000a20| 68 6f 6d 65 6f 6d 6f 72 | 70 68 69 63 0a 74 6f 20 |homeomor|phic.to |
|00000a30| 24 4b 5f 7b 33 2c 33 7d | 24 20 6f 72 20 24 4b 5f |$K_{3,3}|$ or $K_|
|00000a40| 35 24 20 28 61 73 20 61 | 20 6c 69 73 74 20 5c 50 |5$ (as a| list \P|
|00000a50| 42 7b 5c 7c 50 7d 20 6f | 66 20 65 64 67 65 73 29 |B{\|P} o|f edges)|
|00000a60| 2e 20 46 6f 72 20 61 20 | 70 6c 61 6e 61 72 20 67 |. For a |planar g|
|00000a70| 72 61 70 68 0a 5c 50 42 | 7b 5c 7c 47 7d 20 74 68 |raph.\PB|{\|G} th|
|00000a80| 65 20 72 75 6e 6e 69 6e | 67 20 74 69 6d 65 20 6f |e runnin|g time o|
|00000a90| 66 0a 62 6f 74 68 20 76 | 65 72 73 69 6f 6e 73 20 |f.both v|ersions |
|00000aa0| 69 73 20 6c 69 6e 65 61 | 72 20 28 63 66 2e 5c 20 |is linea|r (cf.\ |
|00000ab0| 73 65 63 74 69 6f 6e 20 | 5c 72 65 66 7b 45 66 66 |section |\ref{Eff|
|00000ac0| 69 63 69 65 6e 63 79 7d | 20 66 6f 72 20 6d 6f 72 |iciency}| for mor|
|00000ad0| 65 0a 64 65 74 61 69 6c | 65 64 20 69 6e 66 6f 72 |e.detail|ed infor|
|00000ae0| 6d 61 74 69 6f 6e 29 2e | 20 46 6f 72 20 6e 6f 6e |mation).| For non|
|00000af0| 2d 70 6c 61 6e 61 72 20 | 67 72 61 70 68 73 20 5c |-planar |graphs \|
|00000b00| 50 42 7b 5c 7c 47 7d 20 | 74 68 65 0a 66 69 72 73 |PB{\|G} |the.firs|
|00000b10| 74 20 76 65 72 73 69 6f | 6e 20 72 75 6e 73 20 69 |t versio|n runs i|
|00000b20| 6e 20 6c 69 6e 65 61 72 | 20 74 69 6d 65 20 62 75 |n linear| time bu|
|00000b30| 74 20 74 68 65 20 73 65 | 63 6f 6e 64 20 76 65 72 |t the se|cond ver|
|00000b40| 73 69 6f 6e 20 72 75 6e | 73 20 69 6e 0a 71 75 61 |sion run|s in.qua|
|00000b50| 64 72 61 74 69 63 20 74 | 69 6d 65 2e 0a 57 65 20 |dratic t|ime..We |
|00000b60| 61 72 65 20 61 77 61 72 | 65 20 6f 66 20 74 68 65 |are awar|e of the|
|00000b70| 20 6c 69 6e 65 61 72 20 | 74 69 6d 65 20 61 6c 67 | linear |time alg|
|00000b80| 6f 72 69 74 68 6d 20 6f | 66 20 57 69 6c 6c 69 61 |orithm o|f Willia|
|00000b90| 6d 73 6f 6e 0a 5c 63 69 | 74 65 7b 57 69 6c 6c 69 |mson.\ci|te{Willi|
|00000ba0| 61 6d 73 6f 6e 3a 4b 75 | 72 61 74 6f 77 73 6b 69 |amson:Ku|ratowski|
|00000bb0| 7d 20 74 6f 20 66 69 6e | 64 20 4b 75 72 61 74 6f |} to fin|d Kurato|
|00000bc0| 77 73 6b 69 20 73 75 62 | 67 72 61 70 68 73 20 62 |wski sub|graphs b|
|00000bd0| 75 74 20 68 61 76 65 0a | 6e 6f 74 20 69 6d 70 6c |ut have.|not impl|
|00000be0| 65 6d 65 6e 74 65 64 20 | 69 74 2e 0a 0a 54 68 65 |emented |it...The|
|00000bf0| 20 69 6d 70 6c 65 6d 65 | 6e 74 61 74 69 6f 6e 20 | impleme|ntation |
|00000c00| 6f 66 20 5c 50 42 7b 5c | 5c 7b 70 6c 61 6e 61 72 |of \PB{\|\{planar|
|00000c10| 7d 7d 20 69 73 20 62 61 | 73 65 64 20 6f 6e 20 74 |}} is ba|sed on t|
|00000c20| 68 65 20 4c 45 44 41 20 | 70 6c 61 74 66 6f 72 6d |he LEDA |platform|
|00000c30| 20 6f 66 0a 63 6f 6d 62 | 69 6e 61 74 6f 72 69 61 | of.comb|inatoria|
|00000c40| 6c 0a 61 6e 64 20 67 65 | 6f 6d 65 74 72 69 63 20 |l.and ge|ometric |
|00000c50| 63 6f 6d 70 75 74 69 6e | 67 20 5c 63 69 74 65 7b |computin|g \cite{|
|00000c60| 4c 45 44 41 2d 4d 61 6e | 75 61 6c 2c 4d 65 68 6c |LEDA-Man|ual,Mehl|
|00000c70| 68 6f 72 6e 2d 4e 61 65 | 68 65 72 3a 4c 45 44 41 |horn-Nae|her:LEDA|
|00000c80| 7d 2e 20 49 74 20 69 73 | 20 70 61 72 74 20 6f 66 |}. It is| part of|
|00000c90| 0a 74 68 65 20 4c 45 44 | 41 2d 64 69 73 74 72 69 |.the LED|A-distri|
|00000ca0| 62 75 74 69 6f 6e 20 28 | 61 76 61 69 6c 61 62 6c |bution (|availabl|
|00000cb0| 65 20 74 68 72 6f 75 67 | 68 20 61 6e 6f 6e 79 6d |e throug|h anonym|
|00000cc0| 6f 75 73 20 66 74 70 20 | 61 74 20 63 73 2e 75 6e |ous ftp |at cs.un|
|00000cd0| 69 2d 73 62 2e 64 65 29 | 2e 20 49 6e 0a 74 68 69 |i-sb.de)|. In.thi|
|00000ce0| 73 20 64 6f 63 75 6d 65 | 6e 74 20 77 65 20 64 65 |s docume|nt we de|
|00000cf0| 73 63 72 69 62 65 20 74 | 68 65 20 69 6d 70 6c 65 |scribe t|he imple|
|00000d00| 6d 65 6e 74 61 74 69 6f | 6e 20 6f 66 20 62 6f 74 |mentatio|n of bot|
|00000d10| 68 20 76 65 72 73 69 6f | 6e 73 20 6f 66 20 5c 50 |h versio|ns of \P|
|00000d20| 42 7b 25 0a 5c 5c 7b 70 | 6c 61 6e 61 72 7d 7d 20 |B{%.\\{p|lanar}} |
|00000d30| 61 6e 64 20 61 20 64 65 | 6d 6f 2c 20 61 6e 64 20 |and a de|mo, and |
|00000d40| 72 65 70 6f 72 74 20 6f | 6e 0a 6f 75 72 20 65 78 |report o|n.our ex|
|00000d50| 70 65 72 69 6d 65 6e 74 | 61 6c 20 65 78 70 65 72 |periment|al exper|
|00000d60| 69 65 6e 63 65 2e 0a 0a | 50 72 6f 63 65 64 75 72 |ience...|Procedur|
|00000d70| 65 20 5c 50 42 7b 5c 5c | 7b 70 6c 61 6e 61 72 7d |e \PB{\\|{planar}|
|00000d80| 7d 20 69 73 20 62 61 73 | 65 64 20 6f 6e 20 74 68 |} is bas|ed on th|
|00000d90| 65 0a 48 6f 70 63 72 6f | 66 74 20 61 6e 64 20 54 |e.Hopcro|ft and T|
|00000da0| 61 72 6a 61 6e 20 6c 69 | 6e 65 61 72 20 74 69 6d |arjan li|near tim|
|00000db0| 65 20 70 6c 61 6e 61 72 | 69 74 79 20 74 65 73 74 |e planar|ity test|
|00000dc0| 69 6e 67 20 61 6c 67 6f | 72 69 74 68 6d 20 61 73 |ing algo|rithm as|
|00000dd0| 0a 64 65 73 63 72 69 62 | 65 64 20 69 6e 20 5c 63 |.describ|ed in \c|
|00000de0| 69 74 65 5b 73 65 63 74 | 69 6f 6e 20 49 56 2e 31 |ite[sect|ion IV.1|
|00000df0| 30 5d 7b 4d 65 3a 62 6f | 6f 6b 7d 2e 20 46 6f 72 |0]{Me:bo|ok}. For|
|00000e00| 20 74 68 65 20 73 65 71 | 75 65 6c 20 77 65 20 61 | the seq|uel we a|
|00000e10| 73 73 75 6d 65 0a 6b 6e | 6f 77 6c 65 64 67 65 20 |ssume.kn|owledge |
|00000e20| 6f 66 20 73 65 63 74 69 | 6f 6e 20 49 56 2e 31 30 |of secti|on IV.10|
|00000e30| 20 6f 66 20 5c 63 69 74 | 65 7b 4d 65 3a 62 6f 6f | of \cit|e{Me:boo|
|00000e40| 6b 7d 2e 20 41 20 72 65 | 76 69 73 65 64 20 76 65 |k}. A re|vised ve|
|00000e50| 72 73 69 6f 6e 20 6f 66 | 20 74 68 61 74 20 73 65 |rsion of| that se|
|00000e60| 63 74 69 6f 6e 0a 69 73 | 20 69 6e 63 6c 75 64 65 |ction.is| include|
|00000e70| 64 20 69 6e 20 74 68 69 | 73 20 64 6f 63 75 6d 65 |d in thi|s docume|
|00000e80| 6e 74 20 28 73 65 65 20 | 73 65 63 74 69 6f 6e 20 |nt (see |section |
|00000e90| 5c 72 65 66 7b 72 65 70 | 72 69 6e 74 7d 29 20 66 |\ref{rep|rint}) f|
|00000ea0| 6f 72 20 74 68 65 20 63 | 6f 6e 76 65 6e 69 65 6e |or the c|onvenien|
|00000eb0| 63 65 0a 6f 66 20 74 68 | 65 20 72 65 61 64 65 72 |ce.of th|e reader|
|00000ec0| 2e 20 4f 75 72 20 70 72 | 6f 63 65 64 75 72 65 20 |. Our pr|ocedure |
|00000ed0| 5c 50 42 7b 5c 5c 7b 70 | 6c 61 6e 61 72 7d 7d 20 |\PB{\\{p|lanar}} |
|00000ee0| 64 69 66 66 65 72 73 20 | 66 72 6f 6d 20 5c 63 69 |differs |from \ci|
|00000ef0| 74 65 5b 73 65 63 74 69 | 6f 6e 0a 49 56 2e 31 30 |te[secti|on.IV.10|
|00000f00| 5d 7b 4d 65 3a 62 6f 6f | 6b 7d 0a 69 6e 20 74 77 |]{Me:boo|k}.in tw|
|00000f10| 6f 20 72 65 73 70 65 63 | 74 73 3a 20 46 69 72 73 |o respec|ts: Firs|
|00000f20| 74 6c 79 2c 20 69 74 20 | 77 6f 72 6b 73 20 66 6f |tly, it |works fo|
|00000f30| 72 20 61 72 62 69 74 72 | 61 72 79 20 64 69 72 65 |r arbitr|ary dire|
|00000f40| 63 74 65 64 20 67 72 61 | 70 68 73 20 61 6e 64 0a |cted gra|phs and.|
|00000f50| 6e 6f 74 20 6f 6e 6c 79 | 20 66 6f 72 20 62 69 63 |not only| for bic|
|00000f60| 6f 6e 6e 65 63 74 65 64 | 0a 75 6e 64 69 72 65 63 |onnected|.undirec|
|00000f70| 74 65 64 20 67 72 61 70 | 68 73 2e 20 54 6f 20 74 |ted grap|hs. To t|
|00000f80| 68 69 73 20 65 6e 64 20 | 77 65 20 61 75 67 6d 65 |his end |we augme|
|00000f90| 6e 74 20 74 68 65 20 69 | 6e 70 75 74 20 67 72 61 |nt the i|nput gra|
|00000fa0| 70 68 20 62 79 20 61 64 | 64 69 74 69 6f 6e 61 6c |ph by ad|ditional|
|00000fb0| 20 65 64 67 65 73 0a 74 | 6f 20 6d 61 6b 65 20 69 | edges.t|o make i|
|00000fc0| 74 20 62 69 63 6f 6e 6e | 65 63 74 65 64 20 61 6e |t biconn|ected an|
|00000fd0| 64 20 62 69 64 69 72 65 | 63 74 65 64 2e 20 54 68 |d bidire|cted. Th|
|00000fe0| 65 20 61 75 67 6d 65 6e | 74 61 74 69 6f 6e 20 64 |e augmen|tation d|
|00000ff0| 6f 65 73 20 6e 6f 74 20 | 64 65 73 74 72 6f 79 0a |oes not |destroy.|
|00001000| 70 6c 61 6e 61 72 69 74 | 79 2e 20 53 65 63 6f 6e |planarit|y. Secon|
|00001010| 64 6c 79 2c 20 74 68 65 | 20 65 6d 62 65 64 64 69 |dly, the| embeddi|
|00001020| 6e 67 0a 70 68 61 73 65 | 20 66 6f 6c 6c 6f 77 73 |ng.phase| follows|
|00001030| 20 74 68 65 0a 70 72 65 | 73 65 6e 74 61 74 69 6f | the.pre|sentatio|
|00001040| 6e 20 69 6e 20 5c 63 69 | 74 65 7b 4d 65 68 6c 68 |n in \ci|te{Mehlh|
|00001050| 6f 72 6e 2d 4d 75 74 7a | 65 6c 3a 65 6d 62 65 64 |orn-Mutz|el:embed|
|00001060| 64 69 6e 67 7d 2e 20 57 | 65 20 77 61 6e 74 20 74 |ding}. W|e want t|
|00001070| 6f 20 72 65 6d 61 72 6b | 20 74 68 61 74 20 74 68 |o remark| that th|
|00001080| 65 0a 64 65 73 63 72 69 | 70 74 69 6f 6e 20 6f 66 |e.descri|ption of|
|00001090| 20 74 68 65 20 65 6d 62 | 65 64 64 69 6e 67 20 70 | the emb|edding p|
|000010a0| 68 61 73 65 20 67 69 76 | 65 6e 0a 69 6e 20 5c 63 |hase giv|en.in \c|
|000010b0| 69 74 65 5b 73 65 63 74 | 69 6f 6e 20 49 56 2e 31 |ite[sect|ion IV.1|
|000010c0| 30 5d 7b 4d 65 3a 62 6f | 6f 6b 7d 20 69 73 20 66 |0]{Me:bo|ok} is f|
|000010d0| 61 6c 73 65 2e 0a 54 68 | 65 20 65 73 73 65 6e 74 |alse..Th|e essent|
|000010e0| 69 61 6c 20 70 61 72 74 | 20 6f 66 20 5c 63 69 74 |ial part| of \cit|
|000010f0| 65 7b 4d 65 68 6c 68 6f | 72 6e 2d 4d 75 74 7a 65 |e{Mehlho|rn-Mutze|
|00001100| 6c 3a 65 6d 62 65 64 64 | 69 6e 67 7d 20 69 73 20 |l:embedd|ing} is |
|00001110| 72 65 70 72 69 6e 74 65 | 64 20 69 6e 0a 73 65 63 |reprinte|d in.sec|
|00001120| 74 69 6f 6e 20 5c 72 65 | 66 7b 65 6d 62 65 64 64 |tion \re|f{embedd|
|00001130| 69 6e 67 7d 2e 0a 0a 0a | 54 68 69 73 20 64 6f 63 |ing}....|This doc|
|00001140| 75 6d 65 6e 74 20 64 65 | 66 69 6e 65 73 20 74 68 |ument de|fines th|
|00001150| 65 20 66 69 6c 65 73 20 | 5c 50 42 7b 24 5c 5c 7b |e files |\PB{$\\{|
|00001160| 70 6c 61 6e 61 72 7d 2e | 5c 7c 68 24 7d 2c 20 5c |planar}.|\|h$}, \|
|00001170| 50 42 7b 24 5c 5c 7b 70 | 6c 61 6e 61 72 7d 2e 5c |PB{$\\{p|lanar}.\|
|00001180| 7c 63 24 7d 2c 0a 61 6e | 64 20 5c 50 42 7b 24 5c ||c$},.an|d \PB{$\|
|00001190| 5c 7b 64 65 6d 6f 7d 2e | 5c 7c 63 24 7d 2e 0a 5c |\{demo}.|\|c$}..\|
|000011a0| 50 42 7b 24 5c 5c 7b 70 | 6c 61 6e 61 72 7d 2e 5c |PB{$\\{p|lanar}.\|
|000011b0| 7c 63 24 7d 20 63 6f 6e | 74 61 69 6e 73 20 74 68 ||c$} con|tains th|
|000011c0| 65 20 63 6f 64 65 20 66 | 6f 72 20 70 72 6f 63 65 |e code f|or proce|
|000011d0| 64 75 72 65 20 5c 50 42 | 7b 5c 5c 7b 70 6c 61 6e |dure \PB|{\\{plan|
|000011e0| 61 72 7d 7d 2c 20 5c 50 | 42 7b 24 25 0a 5c 5c 7b |ar}}, \P|B{$%.\\{|
|000011f0| 64 65 6d 6f 7d 2e 5c 7c | 63 24 7d 0a 63 6f 6e 74 |demo}.\||c$}.cont|
|00001200| 61 69 6e 73 20 74 68 65 | 20 63 6f 64 65 20 66 6f |ains the| code fo|
|00001210| 72 20 61 20 64 65 6d 6f | 2c 20 61 6e 64 20 5c 50 |r a demo|, and \P|
|00001220| 42 7b 24 5c 5c 7b 70 6c | 61 6e 61 72 7d 2e 5c 7c |B{$\\{pl|anar}.\||
|00001230| 68 24 7d 20 63 6f 6e 73 | 69 73 74 73 20 6f 66 20 |h$} cons|ists of |
|00001240| 74 68 65 0a 64 65 63 6c | 61 72 61 74 69 6f 6e 73 |the.decl|arations|
|00001250| 20 6f 66 20 70 72 6f 63 | 65 64 75 72 65 20 5c 50 | of proc|edure \P|
|00001260| 42 7b 5c 5c 7b 70 6c 61 | 6e 61 72 7d 7d 2e 0a 54 |B{\\{pla|nar}}..T|
|00001270| 68 65 20 74 68 69 72 64 | 20 66 69 6c 65 20 69 73 |he third| file is|
|00001280| 20 64 65 66 69 6e 65 64 | 20 69 6e 20 73 65 63 74 | defined| in sect|
|00001290| 69 6f 6e 20 5c 72 65 66 | 7b 64 65 6d 6f 7d 2c 20 |ion \ref|{demo}, |
|000012a0| 74 68 65 20 73 74 72 75 | 63 74 75 72 65 20 6f 66 |the stru|cture of|
|000012b0| 20 74 68 65 20 66 69 72 | 73 74 20 74 77 6f 0a 66 | the fir|st two.f|
|000012c0| 69 6c 65 73 0a 69 73 20 | 61 73 20 66 6f 6c 6c 6f |iles.is |as follo|
|000012d0| 77 73 3a 0a 0a 5c 59 5c | 42 5c 34 5c 58 31 3a 5c |ws:..\Y\|B\4\X1:\|
|000012e0| 2e 7b 70 6c 61 6e 61 72 | 2e 68 20 7d 5c 58 24 7b |.{planar|.h }\X${|
|000012f0| 7d 5c 45 7b 7d 24 5c 36 | 0a 5c 26 7b 62 6f 6f 6c |}\E{}$\6|.\&{bool|
|00001300| 7d 20 5c 5c 7b 70 6c 61 | 6e 61 72 7d 28 5c 26 7b |} \\{pla|nar}(\&{|
|00001310| 67 72 61 70 68 7d 20 24 | 7b 7d 7b 5c 41 4e 44 7d |graph} $|{}{\AND}|
|00001320| 5c 7c 47 2c 5c 33 39 7b | 7d 24 5c 26 7b 62 6f 6f |\|G,\39{|}$\&{boo|
|00001330| 6c 7d 20 5c 5c 7b 65 6d | 62 65 64 7d 24 7b 7d 5c |l} \\{em|bed}${}\|
|00001340| 4b 25 0a 5c 5c 7b 66 61 | 6c 73 65 7d 29 3b 7b 7d |K%.\\{fa|lse});{}|
|00001350| 24 5c 36 0a 5c 26 7b 62 | 6f 6f 6c 7d 20 5c 5c 7b |$\6.\&{b|ool} \\{|
|00001360| 70 6c 61 6e 61 72 7d 28 | 5c 26 7b 67 72 61 70 68 |planar}(|\&{graph|
|00001370| 7d 20 24 7b 7d 7b 5c 41 | 4e 44 7d 5c 7c 47 2c 5c |} ${}{\A|ND}\|G,\|
|00001380| 33 39 5c 26 7b 6c 69 73 | 74 7d 5c 6c 61 6e 67 6c |39\&{lis|t}\langl|
|00001390| 65 5c 26 7b 65 64 67 65 | 7d 5c 72 61 6e 67 6c 65 |e\&{edge|}\rangle|
|000013a0| 7b 7d 24 0a 24 7b 7d 7b | 5c 41 4e 44 7d 5c 7c 50 |{}$.${}{|\AND}\|P|
|000013b0| 2c 5c 33 39 7b 7d 24 5c | 26 7b 62 6f 6f 6c 7d 20 |,\39{}$\|&{bool} |
|000013c0| 5c 5c 7b 65 6d 62 65 64 | 7d 24 7b 7d 5c 4b 5c 5c |\\{embed|}${}\K\\|
|000013d0| 7b 66 61 6c 73 65 7d 29 | 3b 7b 7d 24 5c 36 0a 5c |{false})|;{}$\6.\|
|000013e0| 26 7b 76 6f 69 64 7d 20 | 5c 5c 7b 4d 61 6b 65 5c |&{void} |\\{Make\|
|000013f0| 5f 62 69 63 6f 6e 6e 65 | 63 74 65 64 5c 5f 67 72 |_biconne|cted\_gr|
|00001400| 61 70 68 7d 28 5c 26 7b | 67 72 61 70 68 7d 20 24 |aph}(\&{|graph} $|
|00001410| 7b 7d 7b 5c 41 4e 44 7d | 5c 7c 47 29 7b 7d 24 3b |{}{\AND}|\|G){}$;|
|00001420| 5c 70 61 72 0a 5c 66 69 | 0a 0a 5c 4d 7b 32 7d 0a |\par.\fi|..\M{2}.|
|00001430| 0a 5c 59 5c 42 5c 34 5c | 58 32 3a 5c 2e 7b 70 6c |.\Y\B\4\|X2:\.{pl|
|00001440| 61 6e 61 72 2e 63 20 7d | 5c 58 24 7b 7d 5c 45 7b |anar.c }|\X${}\E{|
|00001450| 7d 24 5c 36 0a 5c 58 33 | 3a 69 6e 63 6c 75 64 65 |}$\6.\X3|:include|
|00001460| 73 5c 58 3b 5c 36 0a 5c | 58 31 31 3a 74 79 70 65 |s\X;\6.\|X11:type|
|00001470| 64 65 66 73 2c 20 67 6c | 6f 62 61 6c 20 76 61 72 |defs, gl|obal var|
|00001480| 69 61 62 6c 65 73 20 61 | 6e 64 20 63 6c 61 73 73 |iables a|nd class|
|00001490| 20 64 65 63 6c 61 72 61 | 74 69 6f 6e 73 5c 58 3b | declara|tions\X;|
|000014a0| 5c 36 0a 5c 58 39 3a 61 | 75 78 69 6c 69 61 72 79 |\6.\X9:a|uxiliary|
|000014b0| 20 66 75 6e 63 74 69 6f | 6e 73 5c 58 3b 5c 36 0a | functio|ns\X;\6.|
|000014c0| 5c 58 35 3a 66 69 72 73 | 74 20 76 65 72 73 69 6f |\X5:firs|t versio|
|000014d0| 6e 20 6f 66 20 5c 50 42 | 7b 5c 5c 7b 70 6c 61 6e |n of \PB|{\\{plan|
|000014e0| 61 72 7d 7d 5c 58 3b 5c | 36 0a 5c 58 34 3a 73 65 |ar}}\X;\|6.\X4:se|
|000014f0| 63 6f 6e 64 20 76 65 72 | 73 69 6f 6e 20 6f 66 20 |cond ver|sion of |
|00001500| 5c 50 42 7b 5c 5c 7b 70 | 6c 61 6e 61 72 7d 7d 5c |\PB{\\{p|lanar}}\|
|00001510| 58 3b 5c 70 61 72 0a 5c | 66 69 0a 0a 5c 4d 7b 33 |X;\par.\|fi..\M{3|
|00001520| 7d 57 65 20 69 6e 63 6c | 75 64 65 20 70 61 72 74 |}We incl|ude part|
|00001530| 73 20 6f 66 20 4c 45 44 | 41 20 28 77 68 6f 20 77 |s of LED|A (who w|
|00001540| 6f 75 6c 64 20 77 61 6e | 74 20 74 6f 0a 77 6f 72 |ould wan|t to.wor|
|00001550| 6b 20 77 69 74 68 6f 75 | 74 20 69 74 29 20 5c 63 |k withou|t it) \c|
|00001560| 69 74 65 7b 4c 45 44 41 | 2d 4d 61 6e 75 61 6c 2c |ite{LEDA|-Manual,|
|00001570| 4d 65 68 6c 68 6f 72 6e | 2d 4e 61 65 68 65 72 3a |Mehlhorn|-Naeher:|
|00001580| 4c 45 44 41 7d 2e 0a 57 | 65 20 6e 65 65 64 20 73 |LEDA}..W|e need s|
|00001590| 74 61 63 6b 73 2c 20 67 | 72 61 70 68 73 2c 20 61 |tacks, g|raphs, a|
|000015a0| 6e 64 20 67 72 61 70 68 | 20 61 6c 67 6f 72 69 74 |nd graph| algorit|
|000015b0| 68 6d 73 2e 0a 0a 5c 59 | 5c 42 5c 34 5c 58 33 3a |hms...\Y|\B\4\X3:|
|000015c0| 69 6e 63 6c 75 64 65 73 | 5c 58 24 7b 7d 5c 45 7b |includes|\X${}\E{|
|000015d0| 7d 24 5c 36 0a 5c 38 5c | 23 5c 26 7b 69 6e 63 6c |}$\6.\8\|#\&{incl|
|000015e0| 75 64 65 7d 20 5c 2e 7b | 3c 4c 45 44 41 2f 73 74 |ude} \.{|<LEDA/st|
|000015f0| 61 63 6b 2e 68 3e 7d 5c | 36 0a 5c 38 5c 23 5c 26 |ack.h>}\|6.\8\#\&|
|00001600| 7b 69 6e 63 6c 75 64 65 | 7d 20 5c 2e 7b 3c 4c 45 |{include|} \.{<LE|
|00001610| 44 41 2f 67 72 61 70 68 | 2e 68 3e 7d 5c 36 0a 5c |DA/graph|.h>}\6.\|
|00001620| 38 5c 23 5c 26 7b 69 6e | 63 6c 75 64 65 7d 20 5c |8\#\&{in|clude} \|
|00001630| 2e 7b 3c 4c 45 44 41 2f | 67 72 61 70 68 5c 5f 61 |.{<LEDA/|graph\_a|
|00001640| 6c 67 2e 68 3e 7d 5c 36 | 0a 5c 38 5c 23 5c 26 7b |lg.h>}\6|.\8\#\&{|
|00001650| 69 6e 63 6c 75 64 65 7d | 20 5c 2e 7b 22 70 6c 61 |include}| \.{"pla|
|00001660| 6e 61 72 2e 68 22 7d 5c | 70 61 72 0a 5c 41 33 36 |nar.h"}\|par.\A36|
|00001670| 2e 0a 5c 55 73 32 5c 45 | 54 33 35 2e 5c 66 69 0a |..\Us2\E|T35.\fi.|
|00001680| 0a 5c 4d 7b 34 7d 54 68 | 65 20 73 65 63 6f 6e 64 |.\M{4}Th|e second|
|00001690| 20 76 65 72 73 69 6f 6e | 20 6f 66 20 5c 50 42 7b | version| of \PB{|
|000016a0| 5c 5c 7b 70 6c 61 6e 61 | 72 7d 7d 20 69 73 20 65 |\\{plana|r}} is e|
|000016b0| 61 73 79 20 74 6f 20 64 | 65 73 63 72 69 62 65 2e |asy to d|escribe.|
|000016c0| 20 57 65 20 66 69 72 73 | 74 20 74 65 73 74 0a 74 | We firs|t test.t|
|000016d0| 68 65 0a 70 6c 61 6e 61 | 72 69 74 79 20 6f 66 20 |he.plana|rity of |
|000016e0| 5c 50 42 7b 5c 7c 47 7d | 20 75 73 69 6e 67 20 74 |\PB{\|G}| using t|
|000016f0| 68 65 20 66 69 72 73 74 | 20 76 65 72 73 69 6f 6e |he first| version|
|00001700| 2e 0a 49 66 20 5c 50 42 | 7b 5c 7c 47 7d 20 69 73 |..If \PB|{\|G} is|
|00001710| 20 70 6c 61 6e 61 72 20 | 74 68 65 6e 20 77 65 20 | planar |then we |
|00001720| 61 72 65 20 64 6f 6e 65 | 2e 20 49 66 20 5c 50 42 |are done|. If \PB|
|00001730| 7b 5c 7c 47 7d 20 69 73 | 0a 6e 6f 6e 2d 70 6c 61 |{\|G} is|.non-pla|
|00001740| 6e 61 72 20 74 68 65 6e | 20 77 65 20 63 79 63 6c |nar then| we cycl|
|00001750| 65 20 74 68 72 6f 75 67 | 68 20 74 68 65 20 65 64 |e throug|h the ed|
|00001760| 67 65 73 20 6f 66 20 5c | 50 42 7b 5c 7c 47 7d 2e |ges of \|PB{\|G}.|
|00001770| 20 46 6f 72 20 65 76 65 | 72 79 20 65 64 67 65 20 | For eve|ry edge |
|00001780| 5c 50 42 7b 5c 7c 65 7d | 0a 6f 66 0a 5c 50 42 7b |\PB{\|e}|.of.\PB{|
|00001790| 5c 7c 47 7d 20 77 65 20 | 74 65 73 74 20 74 68 65 |\|G} we |test the|
|000017a0| 20 70 6c 61 6e 61 72 69 | 74 79 20 6f 66 20 5c 50 | planari|ty of \P|
|000017b0| 42 7b 24 5c 7c 47 2d 5c | 7c 65 24 7d 2e 20 49 66 |B{$\|G-\||e$}. If|
|000017c0| 20 5c 50 42 7b 24 5c 7c | 47 2d 5c 7c 65 24 7d 20 | \PB{$\||G-\|e$} |
|000017d0| 69 73 20 70 6c 61 6e 61 | 72 0a 77 65 20 61 64 64 |is plana|r.we add|
|000017e0| 20 5c 50 42 7b 5c 7c 65 | 7d 20 62 61 63 6b 20 69 | \PB{\|e|} back i|
|000017f0| 6e 2e 0a 49 6e 20 74 68 | 69 73 20 77 61 79 20 77 |n..In th|is way w|
|00001800| 65 20 64 65 74 65 72 6d | 69 6e 65 20 61 20 6d 69 |e determ|ine a mi|
|00001810| 6e 69 6d 61 6c 20 28 77 | 69 74 68 20 72 65 73 70 |nimal (w|ith resp|
|00001820| 65 63 74 20 74 6f 20 73 | 65 74 20 69 6e 63 6c 75 |ect to s|et inclu|
|00001830| 73 69 6f 6e 29 0a 6e 6f | 6e 2d 70 6c 61 6e 61 72 |sion).no|n-planar|
|00001840| 20 73 75 62 67 72 61 70 | 68 20 6f 66 20 5c 50 42 | subgrap|h of \PB|
|00001850| 7b 5c 7c 47 7d 2c 20 69 | 2e 65 2e 2c 20 65 69 74 |{\|G}, i|.e., eit|
|00001860| 68 65 72 20 61 20 24 4b | 5f 35 24 20 6f 72 20 61 |her a $K|_5$ or a|
|00001870| 20 24 4b 5f 7b 33 2c 33 | 7d 24 2e 0a 0a 5c 59 5c | $K_{3,3|}$...\Y\|
|00001880| 42 5c 34 5c 58 34 3a 73 | 65 63 6f 6e 64 20 76 65 |B\4\X4:s|econd ve|
|00001890| 72 73 69 6f 6e 20 6f 66 | 20 5c 50 42 7b 5c 5c 7b |rsion of| \PB{\\{|
|000018a0| 70 6c 61 6e 61 72 7d 7d | 5c 58 24 7b 7d 5c 45 7b |planar}}|\X${}\E{|
|000018b0| 7d 24 5c 36 0a 5c 26 7b | 62 6f 6f 6c 7d 20 5c 5c |}$\6.\&{|bool} \\|
|000018c0| 7b 70 6c 61 6e 61 72 7d | 28 5c 26 7b 67 72 61 70 |{planar}|(\&{grap|
|000018d0| 68 7d 20 24 7b 7d 7b 5c | 41 4e 44 7d 5c 7c 47 2c |h} ${}{\|AND}\|G,|
|000018e0| 5c 33 39 5c 26 7b 6c 69 | 73 74 7d 5c 6c 61 6e 67 |\39\&{li|st}\lang|
|000018f0| 6c 65 5c 26 7b 65 64 67 | 65 7d 5c 72 61 6e 67 6c |le\&{edg|e}\rangl|
|00001900| 65 7b 7d 24 0a 24 7b 7d | 7b 5c 41 4e 44 7d 5c 7c |e{}$.${}|{\AND}\||
|00001910| 50 2c 5c 33 39 7b 7d 24 | 5c 26 7b 62 6f 6f 6c 7d |P,\39{}$|\&{bool}|
|00001920| 20 5c 5c 7b 65 6d 62 65 | 64 7d 24 7b 7d 5c 4b 5c | \\{embe|d}${}\K\|
|00001930| 5c 7b 66 61 6c 73 65 7d | 29 7b 7d 24 5c 31 5c 31 |\{false}|){}$\1\1|
|00001940| 5c 32 5c 32 5c 36 0a 24 | 7b 7d 5c 7b 7b 7d 24 5c |\2\2\6.$|{}\{{}$\|
|00001950| 31 5c 36 0a 5c 26 7b 69 | 66 7d 20 24 7b 7d 28 5c |1\6.\&{i|f} ${}(\|
|00001960| 5c 7b 70 6c 61 6e 61 72 | 7d 28 5c 7c 47 2c 5c 33 |\{planar|}(\|G,\3|
|00001970| 39 5c 5c 7b 65 6d 62 65 | 64 7d 29 29 7b 7d 24 5c |9\\{embe|d})){}$\|
|00001980| 31 5c 35 0a 5c 26 7b 72 | 65 74 75 72 6e 7d 20 5c |1\5.\&{r|eturn} \|
|00001990| 5c 7b 74 72 75 65 7d 3b | 5c 43 7b 20 57 65 20 77 |\{true};|\C{ We w|
|000019a0| 6f 72 6b 20 6f 6e 20 61 | 20 63 6f 70 79 20 5c 50 |ork on a| copy \P|
|000019b0| 42 7b 5c 7c 48 7d 20 6f | 66 20 5c 50 42 7b 5c 7c |B{\|H} o|f \PB{\||
|000019c0| 47 7d 20 73 69 6e 63 65 | 20 74 68 65 0a 70 72 6f |G} since| the.pro|
|000019d0| 63 65 64 75 72 65 20 61 | 6c 74 65 72 73 20 5c 50 |cedure a|lters \P|
|000019e0| 42 7b 5c 7c 47 7d 3b 20 | 77 65 20 6c 69 6e 6b 20 |B{\|G}; |we link |
|000019f0| 65 76 65 72 79 20 76 65 | 72 74 65 78 20 61 6e 64 |every ve|rtex and|
|00001a00| 20 65 64 67 65 20 6f 66 | 20 5c 50 42 7b 5c 7c 48 | edge of| \PB{\|H|
|00001a10| 7d 20 77 69 74 68 20 69 | 74 73 0a 6f 72 69 67 69 |} with i|ts.origi|
|00001a20| 6e 61 6c 2e 20 46 6f 72 | 20 74 68 65 20 76 65 72 |nal. For| the ver|
|00001a30| 74 69 63 65 73 20 77 65 | 20 61 6c 73 6f 20 68 61 |tices we| also ha|
|00001a40| 76 65 20 74 68 65 20 72 | 65 76 65 72 73 65 20 6c |ve the r|everse l|
|00001a50| 69 6e 6b 73 2e 20 7d 5c | 32 5c 37 0a 24 7b 7d 5c |inks. }\|2\7.${}\|
|00001a60| 26 7b 47 52 41 50 48 7d | 5c 6c 61 6e 67 6c 65 5c |&{GRAPH}|\langle\|
|00001a70| 26 7b 6e 6f 64 65 7d 2c | 5c 33 39 5c 26 7b 65 64 |&{node},|\39\&{ed|
|00001a80| 67 65 7d 5c 72 61 6e 67 | 6c 65 7b 7d 24 20 5c 7c |ge}\rang|le{}$ \||
|00001a90| 48 3b 5c 36 0a 24 7b 7d | 5c 26 7b 6e 6f 64 65 5c |H;\6.${}|\&{node\|
|00001aa0| 5f 61 72 72 61 79 7d 5c | 6c 61 6e 67 6c 65 5c 26 |_array}\|langle\&|
|00001ab0| 7b 6e 6f 64 65 7d 5c 72 | 61 6e 67 6c 65 7b 7d 24 |{node}\r|angle{}$|
|00001ac0| 20 5c 5c 7b 6c 69 6e 6b | 7d 28 5c 7c 47 29 3b 5c | \\{link|}(\|G);\|
|00001ad0| 36 0a 5c 26 7b 6e 6f 64 | 65 7d 20 5c 7c 76 3b 5c |6.\&{nod|e} \|v;\|
|00001ae0| 37 0a 5c 26 7b 66 6f 72 | 61 6c 6c 5c 5f 6e 6f 64 |7.\&{for|all\_nod|
|00001af0| 65 73 7d 20 24 7b 7d 28 | 5c 7c 76 2c 5c 33 39 5c |es} ${}(|\|v,\39\|
|00001b00| 7c 47 29 7b 7d 24 5c 31 | 5c 35 0a 24 7b 7d 5c 5c ||G){}$\1|\5.${}\\|
|00001b10| 7b 6c 69 6e 6b 7d 5b 5c | 7c 76 5d 5c 4b 5c 7c 48 |{link}[\||v]\K\|H|
|00001b20| 2e 5c 5c 7b 6e 65 77 5c | 5f 6e 6f 64 65 7d 28 5c |.\\{new\|_node}(\|
|00001b30| 7c 76 29 7b 7d 24 3b 5c | 43 7b 20 54 68 69 73 20 ||v){}$;\|C{ This |
|00001b40| 72 65 71 75 69 72 65 73 | 20 73 6f 6d 65 20 65 78 |requires| some ex|
|00001b50| 70 6c 61 6e 61 74 69 6f | 6e 2e 0a 5c 50 42 7b 24 |planatio|n..\PB{$|
|00001b60| 5c 7c 48 2e 5c 5c 7b 6e | 65 77 5c 5f 6e 6f 64 65 |\|H.\\{n|ew\_node|
|00001b70| 7d 28 5c 7c 76 29 24 7d | 20 61 64 64 73 20 61 20 |}(\|v)$}| adds a |
|00001b80| 6e 65 77 20 6e 6f 64 65 | 20 74 6f 20 5c 50 42 7b |new node| to \PB{|
|00001b90| 5c 7c 48 7d 2c 20 72 65 | 74 75 72 6e 73 20 74 68 |\|H}, re|turns th|
|00001ba0| 65 20 6e 65 77 0a 6e 6f | 64 65 2c 20 61 6e 64 20 |e new.no|de, and |
|00001bb0| 6d 61 6b 65 73 20 5c 50 | 42 7b 5c 7c 76 7d 20 74 |makes \P|B{\|v} t|
|00001bc0| 68 65 20 69 6e 66 6f 72 | 6d 61 74 69 6f 6e 20 61 |he infor|mation a|
|00001bd0| 73 73 6f 63 69 61 74 65 | 64 20 77 69 74 68 20 74 |ssociate|d with t|
|00001be0| 68 65 20 6e 65 77 20 6e | 6f 64 65 2e 20 53 6f 20 |he new n|ode. So |
|00001bf0| 74 68 65 0a 73 74 61 74 | 65 6d 65 6e 74 20 63 72 |the.stat|ement cr|
|00001c00| 65 61 74 65 73 20 61 20 | 63 6f 70 79 20 6f 66 20 |eates a |copy of |
|00001c10| 5c 50 42 7b 5c 7c 76 7d | 20 61 6e 64 20 62 69 64 |\PB{\|v}| and bid|
|00001c20| 69 72 65 63 74 69 6f 6e | 61 6c 6c 79 20 6c 69 6e |irection|ally lin|
|00001c30| 6b 73 20 69 74 20 77 69 | 74 68 20 5c 50 42 7b 5c |ks it wi|th \PB{\|
|00001c40| 7c 76 7d 0a 7d 5c 32 5c | 37 0a 5c 26 7b 65 64 67 ||v}.}\2\|7.\&{edg|
|00001c50| 65 7d 20 5c 7c 65 3b 5c | 37 0a 5c 26 7b 66 6f 72 |e} \|e;\|7.\&{for|
|00001c60| 61 6c 6c 5c 5f 65 64 67 | 65 73 7d 20 24 7b 7d 28 |all\_edg|es} ${}(|
|00001c70| 5c 7c 65 2c 5c 33 39 5c | 7c 47 29 7b 7d 24 5c 31 |\|e,\39\||G){}$\1|
|00001c80| 5c 35 0a 24 7b 7d 5c 7c | 48 2e 5c 5c 7b 6e 65 77 |\5.${}\||H.\\{new|
|00001c90| 5c 5f 65 64 67 65 7d 28 | 5c 5c 7b 6c 69 6e 6b 7d |\_edge}(|\\{link}|
|00001ca0| 5b 5c 5c 7b 73 6f 75 72 | 63 65 7d 28 5c 7c 65 29 |[\\{sour|ce}(\|e)|
|00001cb0| 5d 2c 5c 33 39 5c 5c 7b | 6c 69 6e 6b 7d 5b 5c 5c |],\39\\{|link}[\\|
|00001cc0| 7b 74 61 72 67 65 74 7d | 28 5c 7c 65 29 5d 2c 5c |{target}|(\|e)],\|
|00001cd0| 33 39 25 0a 5c 7c 65 29 | 7b 7d 24 3b 5c 43 7b 20 |39%.\|e)|{}$;\C{ |
|00001ce0| 5c 50 42 7b 5c 5c 7b 6c | 69 6e 6b 7d 5b 5c 5c 7b |\PB{\\{l|ink}[\\{|
|00001cf0| 73 6f 75 72 63 65 7d 28 | 5c 7c 65 29 5d 7d 20 61 |source}(|\|e)]} a|
|00001d00| 6e 64 20 5c 50 42 7b 5c | 5c 7b 6c 69 6e 6b 7d 5b |nd \PB{\|\{link}[|
|00001d10| 5c 5c 7b 74 61 72 67 65 | 74 7d 28 5c 7c 65 29 5d |\\{targe|t}(\|e)]|
|00001d20| 7d 0a 61 72 65 20 74 68 | 65 20 63 6f 70 69 65 73 |}.are th|e copies|
|00001d30| 20 6f 66 20 5c 50 42 7b | 5c 5c 7b 73 6f 75 72 63 | of \PB{|\\{sourc|
|00001d40| 65 7d 28 5c 7c 65 29 7d | 20 61 6e 64 20 5c 50 42 |e}(\|e)}| and \PB|
|00001d50| 7b 5c 5c 7b 74 61 72 67 | 65 74 7d 28 5c 7c 65 29 |{\\{targ|et}(\|e)|
|00001d60| 7d 20 69 6e 20 5c 50 42 | 7b 5c 7c 48 7d 2e 0a 54 |} in \PB|{\|H}..T|
|00001d70| 68 65 20 6f 70 65 72 61 | 74 69 6f 6e 20 5c 50 42 |he opera|tion \PB|
|00001d80| 7b 24 5c 7c 48 2e 5c 5c | 7b 6e 65 77 5c 5f 65 64 |{$\|H.\\|{new\_ed|
|00001d90| 67 65 7d 24 7d 20 63 72 | 65 61 74 65 73 20 61 20 |ge}$} cr|eates a |
|00001da0| 6e 65 77 20 65 64 67 65 | 20 77 69 74 68 20 74 68 |new edge| with th|
|00001db0| 65 73 65 20 65 6e 64 70 | 6f 69 6e 74 73 2c 0a 72 |ese endp|oints,.r|
|00001dc0| 65 74 75 72 6e 73 20 69 | 74 2c 20 61 6e 64 20 6d |eturns i|t, and m|
|00001dd0| 61 6b 65 73 20 5c 50 42 | 7b 5c 7c 65 7d 20 74 68 |akes \PB|{\|e} th|
|00001de0| 65 20 69 6e 66 6f 72 6d | 61 74 69 6f 6e 20 6f 66 |e inform|ation of|
|00001df0| 20 74 68 61 74 20 65 64 | 67 65 2e 20 53 6f 20 74 | that ed|ge. So t|
|00001e00| 68 65 20 65 66 66 65 63 | 74 20 6f 66 0a 74 68 65 |he effec|t of.the|
|00001e10| 20 6c 6f 6f 70 20 69 73 | 20 74 6f 20 6d 61 6b 65 | loop is| to make|
|00001e20| 20 74 68 65 20 65 64 67 | 65 20 73 65 74 20 6f 66 | the edg|e set of|
|00001e30| 20 5c 50 42 7b 5c 7c 48 | 7d 20 61 20 63 6f 70 79 | \PB{\|H|} a copy|
|00001e40| 20 6f 66 20 74 68 65 20 | 65 64 67 65 20 73 65 74 | of the |edge set|
|00001e50| 20 6f 66 20 5c 50 42 7b | 5c 7c 47 7d 0a 61 6e 64 | of \PB{|\|G}.and|
|00001e60| 20 74 6f 20 6c 65 74 20 | 65 76 65 72 79 20 65 64 | to let |every ed|
|00001e70| 67 65 20 6f 66 20 5c 50 | 42 7b 5c 7c 48 7d 20 6b |ge of \P|B{\|H} k|
|00001e80| 6e 6f 77 20 69 74 73 20 | 6f 72 69 67 69 6e 61 6c |now its |original|
|00001e90| 2e 20 57 65 20 63 61 6e | 20 6e 6f 77 20 64 65 74 |. We can| now det|
|00001ea0| 65 72 6d 69 6e 65 20 61 | 0a 6d 69 6e 69 6d 61 6c |ermine a|.minimal|
|00001eb0| 20 6e 6f 6e 2d 70 6c 61 | 6e 61 72 20 73 75 62 67 | non-pla|nar subg|
|00001ec0| 72 61 70 68 20 6f 66 20 | 5c 50 42 7b 5c 7c 48 7d |raph of |\PB{\|H}|
|00001ed0| 20 7d 5c 32 5c 37 0a 24 | 7b 7d 5c 26 7b 6c 69 73 | }\2\7.$|{}\&{lis|
|00001ee0| 74 7d 5c 6c 61 6e 67 6c | 65 5c 26 7b 65 64 67 65 |t}\langl|e\&{edge|
|00001ef0| 7d 5c 72 61 6e 67 6c 65 | 7b 7d 24 20 5c 7c 4c 24 |}\rangle|{}$ \|L$|
|00001f00| 7b 7d 5c 4b 5c 7c 48 2e | 5c 5c 7b 61 6c 6c 5c 5f |{}\K\|H.|\\{all\_|
|00001f10| 65 64 67 65 73 7d 28 5c | 2c 29 3b 7b 7d 24 5c 36 |edges}(\|,);{}$\6|
|00001f20| 0a 5c 26 7b 65 64 67 65 | 7d 20 5c 5c 7b 65 68 7d |.\&{edge|} \\{eh}|
|00001f30| 3b 5c 37 0a 5c 26 7b 66 | 6f 72 61 6c 6c 7d 20 24 |;\7.\&{f|orall} $|
|00001f40| 7b 7d 28 5c 5c 7b 65 68 | 7d 2c 5c 33 39 5c 7c 4c |{}(\\{eh|},\39\|L|
|00001f50| 29 7b 7d 24 5c 35 0a 24 | 7b 7d 5c 7b 7b 7d 24 5c |){}$\5.$|{}\{{}$\|
|00001f60| 31 5c 36 0a 24 7b 7d 5c | 7c 65 5c 4b 5c 7c 48 5b |1\6.${}\||e\K\|H[|
|00001f70| 5c 5c 7b 65 68 7d 5d 7b | 7d 24 3b 5c 53 48 43 7b |\\{eh}]{|}$;\SHC{|
|00001f80| 20 74 68 65 20 65 64 67 | 65 20 69 6e 20 5c 50 42 | the edg|e in \PB|
|00001f90| 7b 5c 7c 47 7d 20 63 6f | 72 72 65 73 70 6f 6e 64 |{\|G} co|rrespond|
|00001fa0| 69 6e 67 20 74 6f 20 5c | 50 42 7b 5c 5c 7b 65 68 |ing to \|PB{\\{eh|
|00001fb0| 7d 7d 0a 7d 5c 37 0a 5c | 26 7b 6e 6f 64 65 7d 20 |}}.}\7.\|&{node} |
|00001fc0| 5c 7c 78 24 7b 7d 5c 4b | 5c 5c 7b 73 6f 75 72 63 |\|x${}\K|\\{sourc|
|00001fd0| 65 7d 28 5c 5c 7b 65 68 | 7d 29 3b 7b 7d 24 5c 36 |e}(\\{eh|});{}$\6|
|00001fe0| 0a 5c 26 7b 6e 6f 64 65 | 7d 20 5c 7c 79 24 7b 7d |.\&{node|} \|y${}|
|00001ff0| 5c 4b 5c 5c 7b 74 61 72 | 67 65 74 7d 28 5c 5c 7b |\K\\{tar|get}(\\{|
|00002000| 65 68 7d 29 3b 7b 7d 24 | 5c 37 0a 24 7b 7d 5c 7c |eh});{}$|\7.${}\||
|00002010| 48 2e 5c 5c 7b 64 65 6c | 5c 5f 65 64 67 65 7d 28 |H.\\{del|\_edge}(|
|00002020| 5c 5c 7b 65 68 7d 29 3b | 7b 7d 24 5c 36 0a 5c 26 |\\{eh});|{}$\6.\&|
|00002030| 7b 69 66 7d 20 28 5c 5c | 7b 70 6c 61 6e 61 72 7d |{if} (\\|{planar}|
|00002040| 28 5c 7c 48 29 29 5c 31 | 5c 35 0a 24 7b 7d 5c 7c |(\|H))\1|\5.${}\||
|00002050| 48 2e 5c 5c 7b 6e 65 77 | 5c 5f 65 64 67 65 7d 28 |H.\\{new|\_edge}(|
|00002060| 5c 7c 78 2c 5c 33 39 5c | 7c 79 2c 5c 33 39 5c 7c |\|x,\39\||y,\39\||
|00002070| 65 29 7b 7d 24 3b 5c 53 | 48 43 7b 70 75 74 20 61 |e){}$;\S|HC{put a|
|00002080| 20 6e 65 77 20 76 65 72 | 73 69 6f 6e 20 6f 66 20 | new ver|sion of |
|00002090| 5c 50 42 7b 25 0a 5c 5c | 7b 65 68 7d 7d 20 62 61 |\PB{%.\\|{eh}} ba|
|000020a0| 63 6b 20 69 6e 20 61 6e | 64 20 65 73 74 61 62 6c |ck in an|d establ|
|000020b0| 69 73 68 20 74 68 65 20 | 63 6f 72 72 65 73 70 6f |ish the |correspo|
|000020c0| 6e 64 65 6e 63 65 20 7d | 5c 32 5c 36 0a 5c 34 24 |ndence }|\2\6.\4$|
|000020d0| 7b 7d 5c 7d 7b 7d 24 5c | 43 7b 20 5c 50 42 7b 5c |{}\}{}$\|C{ \PB{\|
|000020e0| 7c 48 7d 20 69 73 20 6e | 6f 77 20 61 20 68 6f 6d ||H} is n|ow a hom|
|000020f0| 65 6f 6d 6f 72 70 68 20 | 6f 66 20 65 69 74 68 65 |eomorph |of eithe|
|00002100| 72 20 24 4b 5f 35 24 20 | 6f 72 20 24 4b 5f 7b 33 |r $K_5$ |or $K_{3|
|00002110| 2c 33 7d 24 2e 20 57 65 | 0a 73 74 69 6c 6c 20 6e |,3}$. We|.still n|
|00002120| 65 65 64 20 74 6f 20 74 | 72 61 6e 73 6c 61 74 65 |eed to t|ranslate|
|00002130| 20 62 61 63 6b 20 74 6f | 20 5c 50 42 7b 5c 7c 47 | back to| \PB{\|G|
|00002140| 7d 2e 20 7d 5c 32 5c 36 | 0a 24 7b 7d 5c 7c 50 2e |}. }\2\6|.${}\|P.|
|00002150| 5c 5c 7b 63 6c 65 61 72 | 7d 28 5c 2c 29 3b 7b 7d |\\{clear|}(\,);{}|
|00002160| 24 5c 36 0a 5c 26 7b 66 | 6f 72 61 6c 6c 5c 5f 65 |$\6.\&{f|orall\_e|
|00002170| 64 67 65 73 7d 20 24 7b | 7d 28 5c 5c 7b 65 68 7d |dges} ${|}(\\{eh}|
|00002180| 2c 5c 33 39 5c 7c 48 29 | 7b 7d 24 5c 31 5c 35 0a |,\39\|H)|{}$\1\5.|
|00002190| 24 7b 7d 5c 7c 50 2e 5c | 5c 7b 61 70 70 65 6e 64 |${}\|P.\|\{append|
|000021a0| 7d 28 5c 7c 48 5b 5c 5c | 7b 65 68 7d 5d 29 3b 7b |}(\|H[\\|{eh}]);{|
|000021b0| 7d 24 5c 32 5c 36 0a 5c | 26 7b 72 65 74 75 72 6e |}$\2\6.\|&{return|
|000021c0| 7d 20 5c 5c 7b 66 61 6c | 73 65 7d 3b 5c 36 0a 5c |} \\{fal|se};\6.\|
|000021d0| 34 24 7b 7d 5c 7d 7b 7d | 24 5c 32 5c 70 61 72 0a |4${}\}{}|$\2\par.|
|000021e0| 5c 55 32 2e 5c 66 69 0a | 0a 5c 4d 7b 35 7d 54 68 |\U2.\fi.|.\M{5}Th|
|000021f0| 65 20 66 69 72 73 74 20 | 76 65 72 73 69 6f 6e 20 |e first |version |
|00002200| 6f 66 20 5c 50 42 7b 5c | 5c 7b 70 6c 61 6e 61 72 |of \PB{\|\{planar|
|00002210| 7d 7d 20 69 73 20 61 6c | 73 6f 20 71 75 69 74 65 |}} is al|so quite|
|00002220| 20 73 69 6d 70 6c 65 20 | 74 6f 20 64 65 73 63 72 | simple |to descr|
|00002230| 69 62 65 2e 0a 47 72 61 | 70 68 73 20 77 69 74 68 |ibe..Gra|phs with|
|00002240| 20 61 74 20 6d 6f 73 74 | 20 74 68 72 65 65 0a 76 | at most| three.v|
|00002250| 65 72 74 69 63 65 73 20 | 61 72 65 20 61 6c 77 61 |ertices |are alwa|
|00002260| 79 73 20 70 6c 61 6e 61 | 72 2e 20 53 6f 20 61 73 |ys plana|r. So as|
|00002270| 73 75 6d 65 20 74 68 61 | 74 20 5c 50 42 7b 5c 7c |sume tha|t \PB{\||
|00002280| 47 7d 20 68 61 73 20 6d | 6f 72 65 20 74 68 61 6e |G} has m|ore than|
|00002290| 20 74 68 72 65 65 0a 76 | 65 72 74 69 63 65 73 2e | three.v|ertices.|
|000022a0| 20 57 65 20 66 69 72 73 | 74 20 61 64 64 20 65 64 | We firs|t add ed|
|000022b0| 67 65 73 20 74 6f 20 5c | 50 42 7b 5c 7c 47 7d 20 |ges to \|PB{\|G} |
|000022c0| 74 6f 20 6d 61 6b 65 20 | 69 74 20 62 69 64 69 72 |to make |it bidir|
|000022d0| 65 63 74 65 64 0a 61 6e | 64 20 74 68 65 6e 20 61 |ected.an|d then a|
|000022e0| 64 64 20 73 6f 6d 65 20 | 6d 6f 72 65 20 65 64 67 |dd some |more edg|
|000022f0| 65 73 20 74 6f 20 6d 61 | 6b 65 0a 69 74 20 62 69 |es to ma|ke.it bi|
|00002300| 63 6f 6e 6e 65 63 74 65 | 64 20 28 6f 66 20 63 6f |connecte|d (of co|
|00002310| 75 72 73 65 2c 20 77 69 | 74 68 6f 75 74 20 64 65 |urse, wi|thout de|
|00002320| 73 74 72 6f 79 69 6e 67 | 20 70 6c 61 6e 61 72 69 |stroying| planari|
|00002330| 74 79 29 2e 20 54 68 65 | 6e 20 77 65 20 74 65 73 |ty). The|n we tes|
|00002340| 74 0a 74 68 65 20 70 6c | 61 6e 61 72 69 74 79 20 |t.the pl|anarity |
|00002350| 6f 66 20 74 68 65 20 65 | 78 74 65 6e 64 65 64 20 |of the e|xtended |
|00002360| 67 72 61 70 68 20 61 6e | 64 20 63 6f 6e 73 74 72 |graph an|d constr|
|00002370| 75 63 74 20 61 6e 20 65 | 6d 62 65 64 64 69 6e 67 |uct an e|mbedding|
|00002380| 2e 0a 53 69 6e 63 65 20 | 5c 50 42 7b 5c 5c 7b 70 |..Since |\PB{\\{p|
|00002390| 6c 61 6e 61 72 7d 7d 20 | 61 6c 74 65 72 73 20 74 |lanar}} |alters t|
|000023a0| 68 65 20 69 6e 70 75 74 | 20 67 72 61 70 68 2c 20 |he input| graph, |
|000023b0| 69 74 20 77 6f 72 6b 73 | 20 6f 6e 20 61 20 63 6f |it works| on a co|
|000023c0| 70 79 20 6f 66 20 69 74 | 2e 0a 0a 0a 0a 5c 59 5c |py of it|.....\Y\|
|000023d0| 42 5c 34 5c 58 35 3a 66 | 69 72 73 74 20 76 65 72 |B\4\X5:f|irst ver|
|000023e0| 73 69 6f 6e 20 6f 66 20 | 5c 50 42 7b 5c 5c 7b 70 |sion of |\PB{\\{p|
|000023f0| 6c 61 6e 61 72 7d 7d 5c | 58 24 7b 7d 5c 45 7b 7d |lanar}}\|X${}\E{}|
|00002400| 24 5c 36 0a 5c 26 7b 62 | 6f 6f 6c 7d 20 5c 5c 7b |$\6.\&{b|ool} \\{|
|00002410| 70 6c 61 6e 61 72 7d 28 | 5c 26 7b 67 72 61 70 68 |planar}(|\&{graph|
|00002420| 7d 20 24 7b 7d 7b 5c 41 | 4e 44 7d 5c 5c 7b 47 69 |} ${}{\A|ND}\\{Gi|
|00002430| 6e 7d 2c 5c 33 39 7b 7d | 24 5c 26 7b 62 6f 6f 6c |n},\39{}|$\&{bool|
|00002440| 7d 20 5c 5c 7b 65 6d 62 | 65 64 7d 24 7b 7d 5c 4b |} \\{emb|ed}${}\K|
|00002450| 25 0a 5c 5c 7b 66 61 6c | 73 65 7d 7b 7d 24 29 5c |%.\\{fal|se}{}$)\|
|00002460| 43 7b 20 5c 50 42 7b 5c | 5c 7b 47 69 6e 7d 7d 20 |C{ \PB{\|\{Gin}} |
|00002470| 69 73 20 61 20 64 69 72 | 65 63 74 65 64 20 67 72 |is a dir|ected gr|
|00002480| 61 70 68 2e 20 5c 50 42 | 7b 5c 5c 7b 70 6c 61 6e |aph. \PB|{\\{plan|
|00002490| 61 72 7d 7d 20 64 65 63 | 69 64 65 73 0a 77 68 65 |ar}} dec|ides.whe|
|000024a0| 74 68 65 72 20 5c 50 42 | 7b 5c 5c 7b 47 69 6e 7d |ther \PB|{\\{Gin}|
|000024b0| 7d 20 69 73 20 70 6c 61 | 6e 61 72 2e 20 49 66 20 |} is pla|nar. If |
|000024c0| 69 74 20 69 73 20 61 6e | 64 20 5c 50 42 7b 24 5c |it is an|d \PB{$\|
|000024d0| 5c 7b 65 6d 62 65 64 7d | 5c 45 5c 5c 7b 74 72 75 |\{embed}|\E\\{tru|
|000024e0| 65 7d 24 7d 20 74 68 65 | 6e 20 69 74 0a 61 6c 73 |e}$} the|n it.als|
|000024f0| 6f 20 63 6f 6d 70 75 74 | 65 73 20 61 20 20 63 6f |o comput|es a  co|
|00002500| 6d 62 69 6e 61 74 6f 72 | 69 61 6c 20 65 6d 62 65 |mbinator|ial embe|
|00002510| 64 64 69 6e 67 20 6f 66 | 20 5c 50 42 7b 5c 5c 7b |dding of| \PB{\\{|
|00002520| 47 69 6e 7d 7d 20 62 79 | 20 73 75 69 74 61 62 6c |Gin}} by| suitabl|
|00002530| 79 20 72 65 6f 72 64 65 | 72 69 6e 67 0a 69 74 73 |y reorde|ring.its|
|00002540| 20 61 64 6a 61 63 65 6e | 63 79 20 6c 69 73 74 73 | adjacen|cy lists|
|00002550| 2e 20 5c 50 42 7b 5c 5c | 7b 47 69 6e 7d 7d 20 6d |. \PB{\\|{Gin}} m|
|00002560| 75 73 74 20 62 65 20 62 | 69 64 69 72 65 63 74 65 |ust be b|idirecte|
|00002570| 64 20 69 6e 20 74 68 61 | 74 20 63 61 73 65 2e 20 |d in tha|t case. |
|00002580| 7d 5c 31 5c 31 5c 36 0a | 24 5c 7b 24 20 5c 26 7b |}\1\1\6.|$\{$ \&{|
|00002590| 69 6e 74 7d 20 5c 7c 6e | 24 7b 7d 5c 4b 5c 5c 7b |int} \|n|${}\K\\{|
|000025a0| 47 69 6e 7d 2e 5c 5c 7b | 6e 75 6d 62 65 72 5c 5f |Gin}.\\{|number\_|
|000025b0| 6f 66 5c 5f 6e 6f 64 65 | 73 7d 28 5c 2c 29 3b 7b |of\_node|s}(\,);{|
|000025c0| 7d 24 5c 37 0a 5c 26 7b | 69 66 7d 20 24 7b 7d 28 |}$\7.\&{|if} ${}(|
|000025d0| 5c 7c 6e 5c 5a 5c 54 7b | 33 7d 29 7b 7d 24 5c 31 |\|n\Z\T{|3}){}$\1|
|000025e0| 5c 35 0a 5c 26 7b 72 65 | 74 75 72 6e 7d 20 5c 5c |\5.\&{re|turn} \\|
|000025f0| 7b 74 72 75 65 7d 3b 5c | 32 5c 36 0a 5c 26 7b 69 |{true};\|2\6.\&{i|
|00002600| 66 7d 20 24 7b 7d 28 5c | 5c 7b 47 69 6e 7d 2e 5c |f} ${}(\|\{Gin}.\|
|00002610| 5c 7b 6e 75 6d 62 65 72 | 5c 5f 6f 66 5c 5f 65 64 |\{number|\_of\_ed|
|00002620| 67 65 73 7d 28 5c 2c 29 | 3e 5c 54 7b 36 7d 2a 5c |ges}(\,)|>\T{6}*\|
|00002630| 7c 6e 2d 5c 54 7b 31 32 | 7d 29 7b 7d 24 5c 31 5c ||n-\T{12|}){}$\1\|
|00002640| 35 0a 5c 26 7b 72 65 74 | 75 72 6e 7d 20 5c 5c 7b |5.\&{ret|urn} \\{|
|00002650| 66 61 6c 73 65 7d 3b 5c | 43 7b 20 41 6e 20 75 6e |false};\|C{ An un|
|00002660| 64 69 72 65 63 74 65 64 | 20 70 6c 61 6e 61 72 20 |directed| planar |
|00002670| 67 72 61 70 68 20 68 61 | 73 20 61 74 20 6d 6f 73 |graph ha|s at mos|
|00002680| 74 20 24 33 6e 2d 36 24 | 20 65 64 67 65 73 3b 20 |t $3n-6$| edges; |
|00002690| 61 0a 64 69 72 65 63 74 | 65 64 20 67 72 61 70 68 |a.direct|ed graph|
|000026a0| 20 6d 61 79 20 68 61 76 | 65 20 74 77 69 63 65 20 | may hav|e twice |
|000026b0| 61 73 20 6d 61 6e 79 20 | 7d 5c 32 5c 36 0a 24 7b |as many |}\2\6.${|
|000026c0| 7d 5c 5c 7b 63 6f 75 74 | 7d 5c 4c 4c 5c 2e 7b 22 |}\\{cout|}\LL\.{"|
|000026d0| 6e 75 6d 62 65 72 5c 20 | 6f 66 5c 20 6e 6f 64 65 |number\ |of\ node|
|000026e0| 73 5c 20 61 6e 64 7d 5c | 29 5c 2e 7b 5c 20 65 64 |s\ and}\|)\.{\ ed|
|000026f0| 67 65 73 5c 20 5c 20 22 | 7d 5c 4c 4c 5c 7c 6e 5c |ges\ \ "|}\LL\|n\|
|00002700| 4c 4c 5c 2e 7b 22 5c 20 | 5c 20 22 7d 25 0a 5c 4c |LL\.{"\ |\ "}%.\L|
|00002710| 4c 5c 5c 7b 47 69 6e 7d | 2e 5c 5c 7b 6e 75 6d 62 |L\\{Gin}|.\\{numb|
|00002720| 65 72 5c 5f 6f 66 5c 5f | 65 64 67 65 73 7d 28 5c |er\_of\_|edges}(\|
|00002730| 2c 29 3b 7b 7d 24 5c 36 | 0a 5c 5c 7b 6e 65 77 6c |,);{}$\6|.\\{newl|
|00002740| 69 6e 65 7d 3b 5c 37 0a | 5c 26 7b 66 6c 6f 61 74 |ine};\7.|\&{float|
|00002750| 7d 20 5c 7c 54 24 7b 7d | 5c 4b 5c 5c 7b 75 73 65 |} \|T${}|\K\\{use|
|00002760| 64 5c 5f 74 69 6d 65 7d | 28 5c 2c 29 3b 7b 7d 24 |d\_time}|(\,);{}$|
|00002770| 5c 37 0a 5c 58 36 3a 6d | 61 6b 65 20 5c 50 42 7b |\7.\X6:m|ake \PB{|
|00002780| 5c 7c 47 7d 20 61 20 63 | 6f 70 79 20 6f 66 20 5c |\|G} a c|opy of \|
|00002790| 50 42 7b 5c 5c 7b 47 69 | 6e 7d 7d 20 61 6e 64 20 |PB{\\{Gi|n}} and |
|000027a0| 61 64 64 20 65 64 67 65 | 73 20 74 6f 20 6d 61 6b |add edge|s to mak|
|000027b0| 65 20 5c 50 42 7b 5c 7c | 47 7d 0a 62 69 64 69 72 |e \PB{\||G}.bidir|
|000027c0| 65 63 74 65 64 5c 58 3b | 5c 36 0a 5c 58 38 3a 6d |ected\X;|\6.\X8:m|
|000027d0| 61 6b 65 20 5c 50 42 7b | 5c 7c 47 7d 20 62 69 63 |ake \PB{|\|G} bic|
|000027e0| 6f 6e 6e 65 63 74 65 64 | 5c 58 3b 5c 36 0a 24 7b |onnected|\X;\6.${|
|000027f0| 7d 5c 5c 7b 63 6f 75 74 | 7d 5c 4c 4c 5c 2e 7b 22 |}\\{cout|}\LL\.{"|
|00002800| 74 69 6d 65 5c 20 74 6f | 5c 20 63 6f 70 79 5c 20 |time\ to|\ copy\ |
|00002810| 61 6e 64 5c 20 74 6f 7d | 5c 29 5c 2e 7b 5c 20 6d |and\ to}|\)\.{\ m|
|00002820| 61 6b 65 5c 20 62 69 64 | 69 72 65 63 74 65 64 5c |ake\ bid|irected\|
|00002830| 20 61 6e 64 7d 5c 29 5c | 2e 7b 5c 0a 63 6f 6e 6e | and}\)\|.{\.conn|
|00002840| 65 63 74 65 64 5c 20 5c | 20 22 7d 5c 4c 4c 5c 5c |ected\ \| "}\LL\\|
|00002850| 7b 75 73 65 64 5c 5f 74 | 69 6d 65 7d 28 5c 7c 54 |{used\_t|ime}(\|T|
|00002860| 29 3b 7b 7d 24 5c 36 0a | 5c 5c 7b 6e 65 77 6c 69 |);{}$\6.|\\{newli|
|00002870| 6e 65 7d 3b 5c 36 0a 5c | 58 31 33 3a 74 65 73 74 |ne};\6.\|X13:test|
|00002880| 20 70 6c 61 6e 61 72 69 | 74 79 5c 58 3b 5c 36 0a | planari|ty\X;\6.|
|00002890| 24 7b 7d 5c 5c 7b 63 6f | 75 74 7d 5c 4c 4c 5c 2e |${}\\{co|ut}\LL\.|
|000028a0| 7b 22 74 69 6d 65 5c 20 | 74 6f 5c 20 74 65 73 74 |{"time\ |to\ test|
|000028b0| 5c 20 70 6c 61 6e 61 72 | 7d 5c 29 5c 2e 7b 69 74 |\ planar|}\)\.{it|
|000028c0| 79 5c 20 5c 20 5c 20 22 | 7d 5c 4c 4c 5c 5c 7b 75 |y\ \ \ "|}\LL\\{u|
|000028d0| 73 65 64 5c 5f 74 69 6d | 65 7d 28 25 0a 5c 7c 54 |sed\_tim|e}(%.\|T|
|000028e0| 29 3b 7b 7d 24 5c 36 0a | 5c 5c 7b 6e 65 77 6c 69 |);{}$\6.|\\{newli|
|000028f0| 6e 65 7d 3b 20 5c 26 7b | 69 66 7d 20 28 5c 5c 7b |ne}; \&{|if} (\\{|
|00002900| 65 6d 62 65 64 7d 29 20 | 24 5c 7b 24 20 5c 26 7b |embed}) |$\{$ \&{|
|00002910| 69 66 7d 20 28 5c 5c 7b | 47 69 6e 5c 5f 69 73 5c |if} (\\{|Gin\_is\|
|00002920| 5f 62 69 64 69 72 65 63 | 74 65 64 7d 29 20 25 0a |_bidirec|ted}) %.|
|00002930| 5c 58 32 36 3a 63 6f 6e | 73 74 72 75 63 74 20 65 |\X26:con|struct e|
|00002940| 6d 62 65 64 64 69 6e 67 | 5c 58 20 5c 36 0a 5c 26 |mbedding|\X \6.\&|
|00002950| 7b 65 6c 73 65 7d 5c 31 | 5c 35 0a 24 7b 7d 5c 5c |{else}\1|\5.${}\\|
|00002960| 7b 65 72 72 6f 72 5c 5f | 68 61 6e 64 6c 65 72 7d |{error\_|handler}|
|00002970| 28 5c 54 7b 32 7d 2c 5c | 33 39 5c 2e 7b 22 73 6f |(\T{2},\|39\.{"so|
|00002980| 72 72 79 3a 5c 20 63 61 | 6e 5c 20 6f 6e 6c 79 5c |rry:\ ca|n\ only\|
|00002990| 20 65 6d 62 7d 5c 29 5c | 2e 7b 65 64 5c 20 62 69 | emb}\)\|.{ed\ bi|
|000029a0| 64 69 72 65 63 74 65 64 | 5c 0a 67 72 61 70 68 73 |directed|\.graphs|
|000029b0| 7d 5c 29 5c 2e 7b 22 7d | 29 3b 7b 7d 24 5c 32 5c |}\)\.{"}|);{}$\2\|
|000029c0| 36 0a 24 7b 7d 5c 5c 7b | 63 6f 75 74 7d 5c 4c 4c |6.${}\\{|cout}\LL|
|000029d0| 5c 2e 7b 22 74 69 6d 65 | 5c 20 74 6f 5c 20 63 6f |\.{"time|\ to\ co|
|000029e0| 6e 73 74 72 75 63 74 5c | 20 65 7d 5c 29 5c 2e 7b |nstruct\| e}\)\.{|
|000029f0| 6d 62 65 64 64 69 6e 67 | 5c 20 5c 20 5c 20 22 7d |mbedding|\ \ \ "}|
|00002a00| 5c 4c 4c 5c 5c 7b 75 73 | 65 64 25 0a 5c 5f 74 69 |\LL\\{us|ed%.\_ti|
|00002a10| 6d 65 7d 28 5c 7c 54 29 | 3b 7b 7d 24 5c 36 0a 5c |me}(\|T)|;{}$\6.\|
|00002a20| 5c 7b 6e 65 77 6c 69 6e | 65 7d 3b 20 24 5c 7d 24 |\{newlin|e}; $\}$|
|00002a30| 20 5c 26 7b 72 65 74 75 | 72 6e 7d 20 5c 5c 7b 74 | \&{retu|rn} \\{t|
|00002a40| 72 75 65 7d 3b 20 24 5c | 7d 7b 7d 24 5c 70 61 72 |rue}; $\|}{}$\par|
|00002a50| 0a 5c 55 32 2e 5c 66 69 | 0a 0a 5c 4d 7b 36 7d 57 |.\U2.\fi|..\M{6}W|
|00002a60| 65 20 6d 61 6b 65 20 5c | 50 42 7b 5c 7c 47 7d 20 |e make \|PB{\|G} |
|00002a70| 61 20 63 6f 70 79 20 6f | 66 20 5c 50 42 7b 5c 5c |a copy o|f \PB{\\|
|00002a80| 7b 47 69 6e 7d 7d 20 61 | 6e 64 20 62 69 64 69 72 |{Gin}} a|nd bidir|
|00002a90| 65 63 74 69 6f 6e 61 6c | 6c 79 20 6c 69 6e 6b 20 |ectional|ly link |
|00002aa0| 61 6c 6c 0a 76 65 72 74 | 69 63 65 73 20 61 6e 64 |all.vert|ices and|
|00002ab0| 0a 65 64 67 65 73 2e 20 | 54 68 65 6e 20 77 65 20 |.edges. |Then we |
|00002ac0| 61 64 64 20 65 64 67 65 | 73 20 74 6f 20 5c 50 42 |add edge|s to \PB|
|00002ad0| 7b 5c 7c 47 7d 20 74 6f | 20 6d 61 6b 65 20 69 74 |{\|G} to| make it|
|00002ae0| 20 62 69 64 69 72 65 63 | 74 65 64 2e 20 49 6e 0a | bidirec|ted. In.|
|00002af0| 5c 50 42 7b 5c 5c 7b 47 | 69 6e 5c 5f 69 73 5c 5f |\PB{\\{G|in\_is\_|
|00002b00| 62 69 64 69 72 65 63 74 | 65 64 7d 7d 20 77 65 20 |bidirect|ed}} we |
|00002b10| 72 65 63 6f 72 64 20 77 | 68 65 74 68 65 72 20 77 |record w|hether w|
|00002b20| 65 20 6e 65 65 64 65 64 | 20 74 6f 20 61 64 64 20 |e needed| to add |
|00002b30| 65 64 67 65 73 2e 0a 0a | 5c 59 5c 42 5c 34 5c 58 |edges...|\Y\B\4\X|
|00002b40| 36 3a 6d 61 6b 65 20 5c | 50 42 7b 5c 7c 47 7d 20 |6:make \|PB{\|G} |
|00002b50| 61 20 63 6f 70 79 20 6f | 66 20 5c 50 42 7b 5c 5c |a copy o|f \PB{\\|
|00002b60| 7b 47 69 6e 7d 7d 20 61 | 6e 64 20 61 64 64 20 65 |{Gin}} a|nd add e|
|00002b70| 64 67 65 73 20 74 6f 20 | 6d 61 6b 65 20 5c 50 42 |dges to |make \PB|
|00002b80| 7b 5c 7c 47 7d 0a 62 69 | 64 69 72 65 63 74 65 64 |{\|G}.bi|directed|
|00002b90| 5c 58 24 7b 7d 5c 45 7b | 7d 24 5c 36 0a 24 5c 26 |\X${}\E{|}$\6.$\&|
|00002ba0| 7b 47 52 41 50 48 7d 5c | 6c 61 6e 67 6c 65 5c 26 |{GRAPH}\|langle\&|
|00002bb0| 7b 6e 6f 64 65 7d 2c 5c | 33 39 5c 26 7b 65 64 67 |{node},\|39\&{edg|
|00002bc0| 65 7d 5c 72 61 6e 67 6c | 65 7b 7d 24 20 5c 7c 47 |e}\rangl|e{}$ \|G|
|00002bd0| 3b 5c 36 0a 24 7b 7d 5c | 26 7b 65 64 67 65 5c 5f |;\6.${}\|&{edge\_|
|00002be0| 61 72 72 61 79 7d 5c 6c | 61 6e 67 6c 65 5c 26 7b |array}\l|angle\&{|
|00002bf0| 65 64 67 65 7d 5c 72 61 | 6e 67 6c 65 7b 7d 24 20 |edge}\ra|ngle{}$ |
|00002c00| 5c 5c 7b 63 6f 6d 70 61 | 6e 69 6f 6e 5c 5f 69 6e |\\{compa|nion\_in|
|00002c10| 5c 5f 47 7d 28 5c 5c 7b | 47 69 6e 7d 29 3b 5c 36 |\_G}(\\{|Gin});\6|
|00002c20| 0a 24 7b 7d 5c 26 7b 6e | 6f 64 65 5c 5f 61 72 72 |.${}\&{n|ode\_arr|
|00002c30| 61 79 7d 5c 6c 61 6e 67 | 6c 65 5c 26 7b 6e 6f 64 |ay}\lang|le\&{nod|
|00002c40| 65 7d 5c 72 61 6e 67 6c | 65 7b 7d 24 20 5c 5c 7b |e}\rangl|e{}$ \\{|
|00002c50| 6c 69 6e 6b 7d 28 5c 5c | 7b 47 69 6e 7d 29 3b 5c |link}(\\|{Gin});\|
|00002c60| 36 0a 5c 26 7b 62 6f 6f | 6c 7d 20 5c 5c 7b 47 69 |6.\&{boo|l} \\{Gi|
|00002c70| 6e 5c 5f 69 73 5c 5f 62 | 69 64 69 72 65 63 74 65 |n\_is\_b|idirecte|
|00002c80| 64 7d 24 7b 7d 5c 4b 5c | 5c 7b 74 72 75 65 7d 3b |d}${}\K\|\{true};|
|00002c90| 7b 7d 24 5c 37 0a 24 7b | 7d 5c 7b 7b 7d 24 5c 31 |{}$\7.${|}\{{}$\1|
|00002ca0| 5c 36 0a 5c 26 7b 6e 6f | 64 65 7d 20 5c 7c 76 3b |\6.\&{no|de} \|v;|
|00002cb0| 5c 37 0a 5c 26 7b 66 6f | 72 61 6c 6c 5c 5f 6e 6f |\7.\&{fo|rall\_no|
|00002cc0| 64 65 73 7d 20 24 7b 7d | 28 5c 7c 76 2c 5c 33 39 |des} ${}|(\|v,\39|
|00002cd0| 5c 5c 7b 47 69 6e 7d 29 | 7b 7d 24 5c 31 5c 35 0a |\\{Gin})|{}$\1\5.|
|00002ce0| 24 7b 7d 5c 5c 7b 6c 69 | 6e 6b 7d 5b 5c 7c 76 5d |${}\\{li|nk}[\|v]|
|00002cf0| 5c 4b 5c 7c 47 2e 5c 5c | 7b 6e 65 77 5c 5f 6e 6f |\K\|G.\\|{new\_no|
|00002d00| 64 65 7d 28 5c 7c 76 29 | 7b 7d 24 3b 5c 53 48 43 |de}(\|v)|{}$;\SHC|
|00002d10| 7b 62 69 64 69 72 65 63 | 74 69 6f 6e 61 6c 20 6c |{bidirec|tional l|
|00002d20| 69 6e 6b 73 20 7d 5c 32 | 5c 37 0a 5c 26 7b 65 64 |inks }\2|\7.\&{ed|
|00002d30| 67 65 7d 20 5c 7c 65 3b | 5c 37 0a 5c 26 7b 66 6f |ge} \|e;|\7.\&{fo|
|00002d40| 72 61 6c 6c 5c 5f 65 64 | 67 65 73 7d 20 24 7b 7d |rall\_ed|ges} ${}|
|00002d50| 28 5c 7c 65 2c 5c 33 39 | 5c 5c 7b 47 69 6e 7d 29 |(\|e,\39|\\{Gin})|
|00002d60| 7b 7d 24 5c 31 5c 35 0a | 24 7b 7d 5c 5c 7b 63 6f |{}$\1\5.|${}\\{co|
|00002d70| 6d 70 61 6e 69 6f 6e 5c | 5f 69 6e 5c 5f 47 7d 5b |mpanion\|_in\_G}[|
|00002d80| 5c 7c 65 5d 5c 4b 5c 7c | 47 2e 5c 5c 7b 6e 65 77 |\|e]\K\||G.\\{new|
|00002d90| 5c 5f 65 64 67 65 7d 28 | 5c 5c 7b 6c 69 6e 6b 7d |\_edge}(|\\{link}|
|00002da0| 5b 5c 5c 7b 73 6f 75 72 | 63 65 7d 28 5c 7c 65 29 |[\\{sour|ce}(\|e)|
|00002db0| 5d 2c 5c 33 39 25 0a 5c | 5c 7b 6c 69 6e 6b 7d 5b |],\39%.\|\{link}[|
|00002dc0| 5c 5c 7b 74 61 72 67 65 | 74 7d 28 5c 7c 65 29 5d |\\{targe|t}(\|e)]|
|00002dd0| 2c 5c 33 39 5c 7c 65 29 | 3b 7b 7d 24 5c 32 5c 36 |,\39\|e)|;{}$\2\6|
|00002de0| 0a 5c 34 24 7b 7d 5c 7d | 7b 7d 24 5c 32 5c 36 0a |.\4${}\}|{}$\2\6.|
|00002df0| 5c 58 37 3a 62 69 64 69 | 72 65 63 74 20 47 5c 58 |\X7:bidi|rect G\X|
|00002e00| 3b 5c 70 61 72 0a 5c 55 | 35 2e 5c 66 69 0a 0a 5c |;\par.\U|5.\fi..\|
|00002e10| 4d 7b 37 7d 57 65 20 62 | 69 64 69 72 65 63 74 20 |M{7}We b|idirect |
|00002e20| 47 2e 20 57 65 20 66 69 | 72 73 74 20 61 73 73 69 |G. We fi|rst assi|
|00002e30| 67 6e 20 6e 75 6d 62 65 | 72 73 20 74 6f 20 6e 6f |gn numbe|rs to no|
|00002e40| 64 65 73 20 61 6e 64 20 | 65 64 67 65 73 2e 20 57 |des and |edges. W|
|00002e50| 65 20 6d 61 6b 65 20 73 | 75 72 65 0a 74 68 61 74 |e make s|ure.that|
|00002e60| 0a 74 68 65 20 74 77 6f | 20 76 65 72 73 69 6f 6e |.the two| version|
|00002e70| 73 20 6f 66 20 74 68 65 | 20 73 61 6d 65 20 75 6e |s of the| same un|
|00002e80| 64 69 72 65 63 74 65 64 | 20 65 64 67 65 20 67 65 |directed| edge ge|
|00002e90| 74 20 74 68 65 20 73 61 | 6d 65 20 6e 75 6d 62 65 |t the sa|me numbe|
|00002ea0| 72 20 62 75 74 20 76 65 | 72 73 69 6f 6e 73 0a 6f |r but ve|rsions.o|
|00002eb0| 66 20 64 69 73 74 69 6e | 63 74 20 75 6e 64 69 72 |f distin|ct undir|
|00002ec0| 65 63 74 65 64 20 65 64 | 67 65 73 20 67 65 74 20 |ected ed|ges get |
|00002ed0| 64 69 66 66 65 72 65 6e | 74 20 6e 75 6d 62 65 72 |differen|t number|
|00002ee0| 73 2e 20 54 68 65 6e 20 | 77 65 20 73 6f 72 74 20 |s. Then |we sort |
|00002ef0| 74 68 65 20 65 64 67 65 | 73 0a 61 63 63 6f 72 64 |the edge|s.accord|
|00002f00| 69 6e 67 20 74 6f 20 6e | 75 6d 62 65 72 73 2e 20 |ing to n|umbers. |
|00002f10| 46 69 6e 61 6c 6c 79 20 | 77 65 20 73 74 65 70 20 |Finally |we step |
|00002f20| 74 68 72 6f 75 67 68 20 | 74 68 65 20 73 6f 72 74 |through |the sort|
|00002f30| 65 64 20 6c 69 73 74 20 | 6f 66 20 65 64 67 65 73 |ed list |of edges|
|00002f40| 0a 61 6e 64 20 61 64 64 | 0a 6d 69 73 73 69 6e 67 |.and add|.missing|
|00002f50| 20 65 64 67 65 73 2e 0a | 0a 0a 5c 59 5c 42 5c 34 | edges..|..\Y\B\4|
|00002f60| 5c 58 37 3a 62 69 64 69 | 72 65 63 74 20 47 5c 58 |\X7:bidi|rect G\X|
|00002f70| 24 7b 7d 5c 45 7b 7d 24 | 5c 36 0a 24 7b 7d 5c 7b |${}\E{}$|\6.${}\{|
|00002f80| 7b 7d 24 5c 31 5c 36 0a | 24 7b 7d 5c 26 7b 6e 6f |{}$\1\6.|${}\&{no|
|00002f90| 64 65 5c 5f 61 72 72 61 | 79 7d 5c 6c 61 6e 67 6c |de\_arra|y}\langl|
|00002fa0| 65 5c 26 7b 69 6e 74 7d | 5c 72 61 6e 67 6c 65 7b |e\&{int}|\rangle{|
|00002fb0| 7d 24 20 5c 5c 7b 6e 72 | 7d 28 5c 7c 47 29 3b 5c |}$ \\{nr|}(\|G);\|
|00002fc0| 36 0a 24 7b 7d 5c 26 7b | 65 64 67 65 5c 5f 61 72 |6.${}\&{|edge\_ar|
|00002fd0| 72 61 79 7d 5c 6c 61 6e | 67 6c 65 5c 26 7b 69 6e |ray}\lan|gle\&{in|
|00002fe0| 74 7d 5c 72 61 6e 67 6c | 65 7b 7d 24 20 5c 5c 7b |t}\rangl|e{}$ \\{|
|00002ff0| 63 6f 73 74 7d 28 5c 7c | 47 29 3b 5c 36 0a 5c 26 |cost}(\||G);\6.\&|
|00003000| 7b 69 6e 74 7d 20 5c 5c | 7b 63 75 72 5c 5f 6e 72 |{int} \\|{cur\_nr|
|00003010| 7d 24 7b 7d 5c 4b 5c 54 | 7b 30 7d 3b 7b 7d 24 5c |}${}\K\T|{0};{}$\|
|00003020| 36 0a 5c 26 7b 69 6e 74 | 7d 20 5c 7c 6e 24 7b 7d |6.\&{int|} \|n${}|
|00003030| 5c 4b 5c 7c 47 2e 5c 5c | 7b 6e 75 6d 62 65 72 5c |\K\|G.\\|{number\|
|00003040| 5f 6f 66 5c 5f 6e 6f 64 | 65 73 7d 28 5c 2c 29 3b |_of\_nod|es}(\,);|
|00003050| 7b 7d 24 5c 36 0a 5c 26 | 7b 6e 6f 64 65 7d 20 5c |{}$\6.\&|{node} \|
|00003060| 7c 76 3b 5c 36 0a 5c 26 | 7b 65 64 67 65 7d 20 5c ||v;\6.\&|{edge} \|
|00003070| 7c 65 3b 5c 37 0a 5c 26 | 7b 66 6f 72 61 6c 6c 5c ||e;\7.\&|{forall\|
|00003080| 5f 6e 6f 64 65 73 7d 20 | 24 7b 7d 28 5c 7c 76 2c |_nodes} |${}(\|v,|
|00003090| 5c 33 39 5c 7c 47 29 7b | 7d 24 5c 31 5c 35 0a 24 |\39\|G){|}$\1\5.$|
|000030a0| 7b 7d 5c 5c 7b 6e 72 7d | 5b 5c 7c 76 5d 5c 4b 5c |{}\\{nr}|[\|v]\K\|
|000030b0| 5c 7b 63 75 72 5c 5f 6e | 72 7d 5c 50 50 3b 7b 7d |\{cur\_n|r}\PP;{}|
|000030c0| 24 5c 32 5c 36 0a 5c 26 | 7b 66 6f 72 61 6c 6c 5c |$\2\6.\&|{forall\|
|000030d0| 5f 65 64 67 65 73 7d 20 | 24 7b 7d 28 5c 7c 65 2c |_edges} |${}(\|e,|
|000030e0| 5c 33 39 5c 7c 47 29 7b | 7d 24 5c 31 5c 35 0a 24 |\39\|G){|}$\1\5.$|
|000030f0| 7b 7d 5c 5c 7b 63 6f 73 | 74 7d 5b 5c 7c 65 5d 5c |{}\\{cos|t}[\|e]\|
|00003100| 4b 28 28 5c 5c 7b 6e 72 | 7d 5b 5c 5c 7b 73 6f 75 |K((\\{nr|}[\\{sou|
|00003110| 72 63 65 7d 28 5c 7c 65 | 29 5d 3c 5c 5c 7b 6e 72 |rce}(\|e|)]<\\{nr|
|00003120| 7d 5b 5c 5c 7b 74 61 72 | 67 65 74 7d 28 5c 7c 65 |}[\\{tar|get}(\|e|
|00003130| 29 5d 29 5c 3f 5c 7c 6e | 2a 25 0a 5c 5c 7b 6e 72 |)])\?\|n|*%.\\{nr|
|00003140| 7d 5b 5c 5c 7b 73 6f 75 | 72 63 65 7d 28 5c 7c 65 |}[\\{sou|rce}(\|e|
|00003150| 29 5d 2b 5c 5c 7b 6e 72 | 7d 5b 5c 5c 7b 74 61 72 |)]+\\{nr|}[\\{tar|
|00003160| 67 65 74 7d 28 5c 7c 65 | 29 5d 3a 5c 7c 6e 2a 5c |get}(\|e|)]:\|n*\|
|00003170| 5c 7b 6e 72 7d 5b 5c 5c | 7b 74 61 72 67 65 74 7d |\{nr}[\\|{target}|
|00003180| 28 5c 7c 65 29 5d 2b 25 | 0a 5c 5c 7b 6e 72 7d 5b |(\|e)]+%|.\\{nr}[|
|00003190| 5c 5c 7b 73 6f 75 72 63 | 65 7d 28 5c 7c 65 29 5d |\\{sourc|e}(\|e)]|
|000031a0| 29 3b 7b 7d 24 5c 32 5c | 36 0a 24 7b 7d 5c 7c 47 |);{}$\2\|6.${}\|G|
|000031b0| 2e 5c 5c 7b 73 6f 72 74 | 5c 5f 65 64 67 65 73 7d |.\\{sort|\_edges}|
|000031c0| 28 5c 5c 7b 63 6f 73 74 | 7d 29 3b 7b 7d 24 5c 37 |(\\{cost|});{}$\7|
|000031d0| 0a 24 7b 7d 5c 26 7b 6c | 69 73 74 7d 5c 6c 61 6e |.${}\&{l|ist}\lan|
|000031e0| 67 6c 65 5c 26 7b 65 64 | 67 65 7d 5c 72 61 6e 67 |gle\&{ed|ge}\rang|
|000031f0| 6c 65 7b 7d 24 20 5c 7c | 4c 24 7b 7d 5c 4b 5c 7c |le{}$ \||L${}\K\||
|00003200| 47 2e 5c 5c 7b 61 6c 6c | 5c 5f 65 64 67 65 73 7d |G.\\{all|\_edges}|
|00003210| 28 5c 2c 29 3b 7b 7d 24 | 5c 37 0a 5c 26 7b 77 68 |(\,);{}$|\7.\&{wh|
|00003220| 69 6c 65 7d 20 24 7b 7d | 28 5c 52 5c 7c 4c 2e 5c |ile} ${}|(\R\|L.\|
|00003230| 5c 7b 65 6d 70 74 79 7d | 28 5c 2c 29 29 7b 7d 24 |\{empty}|(\,)){}$|
|00003240| 5c 35 0a 24 7b 7d 5c 7b | 7b 7d 24 5c 31 5c 36 0a |\5.${}\{|{}$\1\6.|
|00003250| 24 7b 7d 5c 7c 65 5c 4b | 5c 7c 4c 2e 5c 5c 7b 70 |${}\|e\K|\|L.\\{p|
|00003260| 6f 70 7d 28 5c 2c 29 7b | 7d 24 3b 5c 43 7b 20 63 |op}(\,){|}$;\C{ c|
|00003270| 68 65 63 6b 20 77 68 65 | 74 68 65 72 20 74 68 65 |heck whe|ther the|
|00003280| 20 66 69 72 73 74 20 65 | 64 67 65 20 6f 6e 20 5c | first e|dge on \|
|00003290| 50 42 7b 5c 7c 4c 7d 20 | 69 73 0a 65 71 75 61 6c |PB{\|L} |is.equal|
|000032a0| 20 74 6f 20 74 68 65 20 | 72 65 76 65 72 73 61 6c | to the |reversal|
|000032b0| 20 6f 66 20 5c 50 42 7b | 5c 7c 65 7d 2e 20 49 66 | of \PB{|\|e}. If|
|000032c0| 20 73 6f 2c 20 64 65 6c | 65 74 65 20 69 74 20 66 | so, del|ete it f|
|000032d0| 72 6f 6d 20 5c 50 42 7b | 5c 7c 4c 7d 2c 20 69 66 |rom \PB{|\|L}, if|
|000032e0| 20 6e 6f 74 2c 20 61 64 | 64 0a 74 68 65 20 72 65 | not, ad|d.the re|
|000032f0| 76 65 72 73 61 6c 20 74 | 6f 20 5c 50 42 7b 5c 7c |versal t|o \PB{\||
|00003300| 47 7d 20 7d 5c 36 0a 5c | 26 7b 69 66 7d 20 24 7b |G} }\6.\|&{if} ${|
|00003310| 7d 28 5c 52 5c 7c 4c 2e | 5c 5c 7b 65 6d 70 74 79 |}(\R\|L.|\\{empty|
|00003320| 7d 28 5c 2c 29 5c 57 28 | 5c 5c 7b 73 6f 75 72 63 |}(\,)\W(|\\{sourc|
|00003330| 65 7d 28 5c 7c 65 29 5c | 45 5c 5c 7b 74 61 72 67 |e}(\|e)\|E\\{targ|
|00003340| 65 74 7d 28 5c 7c 4c 2e | 5c 5c 7b 68 65 61 64 7d |et}(\|L.|\\{head}|
|00003350| 28 5c 2c 29 29 29 25 0a | 5c 57 28 5c 5c 7b 73 6f |(\,)))%.|\W(\\{so|
|00003360| 75 72 63 65 7d 28 5c 7c | 4c 2e 5c 5c 7b 68 65 61 |urce}(\||L.\\{hea|
|00003370| 64 7d 28 5c 2c 29 29 5c | 45 5c 5c 7b 74 61 72 67 |d}(\,))\|E\\{targ|
|00003380| 65 74 7d 28 5c 7c 65 29 | 29 29 7b 7d 24 5c 31 5c |et}(\|e)|)){}$\1\|
|00003390| 35 0a 24 7b 7d 5c 7c 4c | 2e 5c 5c 7b 70 6f 70 7d |5.${}\|L|.\\{pop}|
|000033a0| 28 5c 2c 29 3b 7b 7d 24 | 5c 32 5c 36 0a 5c 26 7b |(\,);{}$|\2\6.\&{|
|000033b0| 65 6c 73 65 7d 5c 35 0a | 24 7b 7d 5c 7b 7b 7d 24 |else}\5.|${}\{{}$|
|000033c0| 5c 31 5c 36 0a 24 7b 7d | 5c 7c 47 2e 5c 5c 7b 6e |\1\6.${}|\|G.\\{n|
|000033d0| 65 77 5c 5f 65 64 67 65 | 7d 28 5c 5c 7b 74 61 72 |ew\_edge|}(\\{tar|
|000033e0| 67 65 74 7d 28 5c 7c 65 | 29 2c 5c 33 39 5c 5c 7b |get}(\|e|),\39\\{|
|000033f0| 73 6f 75 72 63 65 7d 28 | 5c 7c 65 29 29 3b 7b 7d |source}(|\|e));{}|
|00003400| 24 5c 36 0a 24 7b 7d 5c | 5c 7b 47 69 6e 5c 5f 69 |$\6.${}\|\{Gin\_i|
|00003410| 73 5c 5f 62 69 64 69 72 | 65 63 74 65 64 7d 5c 4b |s\_bidir|ected}\K|
|00003420| 5c 5c 7b 66 61 6c 73 65 | 7d 3b 7b 7d 24 5c 36 0a |\\{false|};{}$\6.|
|00003430| 5c 34 24 7b 7d 5c 7d 7b | 7d 24 5c 32 5c 36 0a 5c |\4${}\}{|}$\2\6.\|
|00003440| 34 24 7b 7d 5c 7d 7b 7d | 24 5c 32 5c 36 0a 5c 34 |4${}\}{}|$\2\6.\4|
|00003450| 24 7b 7d 5c 7d 7b 7d 24 | 5c 32 5c 70 61 72 0a 5c |${}\}{}$|\2\par.\|
|00003460| 55 36 2e 5c 66 69 0a 0a | 5c 4e 7b 31 7d 7b 38 7d |U6.\fi..|\N{1}{8}|
|00003470| 4d 61 6b 69 6e 67 20 74 | 68 65 20 47 72 61 70 68 |Making t|he Graph|
|00003480| 20 42 69 63 6f 6e 6e 65 | 63 74 65 64 2e 0a 0a 57 | Biconne|cted...W|
|00003490| 65 20 6d 61 6b 65 20 5c | 50 42 7b 5c 7c 47 7d 20 |e make \|PB{\|G} |
|000034a0| 62 69 63 6f 6e 6e 65 63 | 74 65 64 2e 20 57 65 20 |biconnec|ted. We |
|000034b0| 66 69 72 73 74 20 6d 61 | 6b 65 20 69 74 20 63 6f |first ma|ke it co|
|000034c0| 6e 6e 65 63 74 65 64 20 | 62 79 20 6c 69 6e 6b 69 |nnected |by linki|
|000034d0| 6e 67 20 61 6c 6c 0a 72 | 6f 6f 74 73 2e 20 41 73 |ng all.r|oots. As|
|000034e0| 73 75 6d 65 20 74 68 61 | 74 20 69 73 20 64 6f 6e |sume tha|t is don|
|000034f0| 65 2e 20 4c 65 74 20 24 | 61 24 20 62 65 20 61 6e |e. Let $|a$ be an|
|00003500| 79 20 61 72 74 69 63 75 | 6c 61 74 69 6f 6e 0a 70 |y articu|lation.p|
|00003510| 6f 69 6e 74 20 61 6e 64 | 20 6c 65 74 20 24 75 24 |oint and| let $u$|
|00003520| 20 61 6e 64 20 24 76 24 | 20 62 65 20 6e 65 69 67 | and $v$| be neig|
|00003530| 68 62 6f 72 73 20 6f 66 | 20 24 61 24 20 62 65 6c |hbors of| $a$ bel|
|00003540| 6f 6e 67 69 6e 67 20 74 | 6f 20 64 69 66 66 65 72 |onging t|o differ|
|00003550| 65 6e 74 0a 62 69 63 6f | 6e 6e 65 63 74 65 64 20 |ent.bico|nnected |
|00003560| 63 6f 6d 70 6f 6e 65 6e | 74 73 2e 20 54 68 65 6e |componen|ts. Then|
|00003570| 20 74 68 65 72 65 20 61 | 72 65 20 65 6d 62 65 64 | there a|re embed|
|00003580| 64 69 6e 67 73 20 6f 66 | 20 74 68 65 20 74 77 6f |dings of| the two|
|00003590| 20 63 6f 6d 70 6f 6e 65 | 6e 74 73 0a 77 69 74 68 | compone|nts.with|
|000035a0| 20 74 68 65 20 65 64 67 | 65 73 20 24 5c 7b 75 2c | the edg|es $\{u,|
|000035b0| 61 5c 7d 24 20 61 6e 64 | 20 24 5c 7b 76 2c 61 5c |a\}$ and| $\{v,a\|
|000035c0| 7d 24 20 6f 6e 20 74 68 | 65 20 62 6f 75 6e 64 61 |}$ on th|e bounda|
|000035d0| 72 79 20 6f 66 20 74 68 | 65 20 75 6e 62 6f 75 6e |ry of th|e unboun|
|000035e0| 64 65 64 0a 66 61 63 65 | 2e 20 48 65 6e 63 65 20 |ded.face|. Hence |
|000035f0| 77 65 20 6d 61 79 20 61 | 64 64 20 74 68 65 20 65 |we may a|dd the e|
|00003600| 64 67 65 20 24 5c 7b 75 | 2c 76 5c 7d 24 20 77 69 |dge $\{u|,v\}$ wi|
|00003610| 74 68 6f 75 74 20 64 65 | 73 74 72 6f 79 69 6e 67 |thout de|stroying|
|00003620| 20 70 6c 61 6e 61 72 69 | 74 79 2e 0a 50 72 6f 63 | planari|ty..Proc|
|00003630| 65 65 64 69 6e 67 20 69 | 6e 20 74 68 69 73 20 77 |eeding i|n this w|
|00003640| 61 79 20 77 65 20 6d 61 | 6b 65 20 5c 50 42 7b 5c |ay we ma|ke \PB{\|
|00003650| 7c 47 7d 0a 62 69 63 6f | 6e 6e 65 63 74 65 64 2e ||G}.bico|nnected.|
|00003660| 0a 0a 49 6e 20 5c 50 42 | 7b 5c 5c 7b 4d 61 6b 65 |..In \PB|{\\{Make|
|00003670| 5c 5f 62 69 63 6f 6e 6e | 65 63 74 65 64 5c 5f 67 |\_biconn|ected\_g|
|00003680| 72 61 70 68 7d 7d 20 77 | 65 20 63 68 61 6e 67 65 |raph}} w|e change|
|00003690| 20 74 68 65 20 67 72 61 | 70 68 20 77 68 69 6c 65 | the gra|ph while|
|000036a0| 20 77 6f 72 6b 69 6e 67 | 20 6f 6e 20 69 74 2e 0a | working| on it..|
|000036b0| 42 75 74 20 77 65 20 6d | 6f 64 69 66 79 20 6f 6e |But we m|odify on|
|000036c0| 6c 79 0a 74 68 6f 73 65 | 20 61 64 6a 61 63 65 6e |ly.those| adjacen|
|000036d0| 63 79 20 6c 69 73 74 73 | 20 74 68 61 74 20 77 69 |cy lists| that wi|
|000036e0| 6c 6c 20 6e 6f 74 20 62 | 65 20 74 6f 75 63 68 65 |ll not b|e touche|
|000036f0| 64 20 6c 61 74 65 72 2e | 0a 0a 57 65 20 6e 65 65 |d later.|..We nee|
|00003700| 64 20 74 68 65 20 62 69 | 63 6f 6e 6e 65 63 74 65 |d the bi|connecte|
|00003710| 64 20 76 65 72 73 69 6f | 6e 20 6f 66 20 5c 50 42 |d versio|n of \PB|
|00003720| 7b 5c 7c 47 7d 20 28 5c | 50 42 7b 5c 7c 47 7d 20 |{\|G} (\|PB{\|G} |
|00003730| 77 69 6c 6c 20 62 65 20 | 66 75 72 74 68 65 72 20 |will be |further |
|00003740| 6d 6f 64 69 66 69 65 64 | 0a 64 75 72 69 6e 67 20 |modified|.during |
|00003750| 74 68 65 20 70 6c 61 6e | 61 72 69 74 79 20 74 65 |the plan|arity te|
|00003760| 73 74 29 20 69 6e 20 6f | 72 64 65 72 20 74 6f 20 |st) in o|rder to |
|00003770| 63 6f 6e 73 74 72 75 63 | 74 20 74 68 65 20 70 6c |construc|t the pl|
|00003780| 61 6e 61 72 20 65 6d 62 | 65 64 64 69 6e 67 2e 20 |anar emb|edding. |
|00003790| 53 6f 20 77 65 0a 73 74 | 6f 72 65 20 69 74 20 61 |So we.st|ore it a|
|000037a0| 73 20 61 20 67 72 61 70 | 68 20 5c 50 42 7b 5c 7c |s a grap|h \PB{\||
|000037b0| 48 7d 2e 20 46 6f 72 20 | 65 76 65 72 79 20 65 64 |H}. For |every ed|
|000037c0| 67 65 20 6f 66 20 5c 50 | 42 7b 5c 5c 7b 47 69 6e |ge of \P|B{\\{Gin|
|000037d0| 7d 7d 20 61 6e 64 20 5c | 50 42 7b 5c 7c 47 7d 20 |}} and \|PB{\|G} |
|000037e0| 77 65 0a 73 74 6f 72 65 | 20 61 20 6c 69 6e 6b 20 |we.store| a link |
|000037f0| 74 6f 0a 69 74 73 20 63 | 6f 70 79 20 69 6e 20 5c |to.its c|opy in \|
|00003800| 50 42 7b 5c 7c 48 7d 2e | 20 49 6e 20 61 64 64 69 |PB{\|H}.| In addi|
|00003810| 74 69 6f 6e 20 65 76 65 | 72 79 20 65 64 67 65 20 |tion eve|ry edge |
|00003820| 6f 66 20 5c 50 42 7b 5c | 7c 48 7d 20 69 73 20 6d |of \PB{\||H} is m|
|00003830| 61 64 65 20 74 6f 20 6b | 6e 6f 77 20 69 74 73 0a |ade to k|now its.|
|00003840| 72 65 76 65 72 73 61 6c | 2e 0a 0a 5c 59 5c 42 5c |reversal|...\Y\B\|
|00003850| 34 5c 58 38 3a 6d 61 6b | 65 20 5c 50 42 7b 5c 7c |4\X8:mak|e \PB{\||
|00003860| 47 7d 20 62 69 63 6f 6e | 6e 65 63 74 65 64 5c 58 |G} bicon|nected\X|
|00003870| 24 7b 7d 5c 45 7b 7d 24 | 5c 36 0a 5c 5c 7b 4d 61 |${}\E{}$|\6.\\{Ma|
|00003880| 6b 65 5c 5f 62 69 63 6f | 6e 6e 65 63 74 65 64 5c |ke\_bico|nnected\|
|00003890| 5f 67 72 61 70 68 7d 28 | 5c 7c 47 29 3b 5c 36 0a |_graph}(|\|G);\6.|
|000038a0| 5c 58 31 32 3a 6d 61 6b | 65 20 5c 50 42 7b 5c 7c |\X12:mak|e \PB{\||
|000038b0| 48 7d 20 61 20 63 6f 70 | 79 20 6f 66 20 5c 50 42 |H} a cop|y of \PB|
|000038c0| 7b 5c 7c 47 7d 5c 58 3b | 5c 70 61 72 0a 5c 55 35 |{\|G}\X;|\par.\U5|
|000038d0| 2e 5c 66 69 0a 0a 5c 4d | 7b 39 7d 57 65 20 67 69 |.\fi..\M|{9}We gi|
|000038e0| 76 65 20 74 68 65 20 64 | 65 74 61 69 6c 73 20 6f |ve the d|etails o|
|000038f0| 66 20 74 68 65 20 70 72 | 6f 63 65 64 75 72 65 20 |f the pr|ocedure |
|00003900| 5c 50 42 7b 5c 5c 7b 4d | 61 6b 65 5c 5f 62 69 63 |\PB{\\{M|ake\_bic|
|00003910| 6f 6e 6e 65 63 74 65 64 | 5c 5f 67 72 61 70 68 7d |onnected|\_graph}|
|00003920| 7d 2e 20 57 65 0a 66 69 | 72 73 74 20 6d 61 6b 65 |}. We.fi|rst make|
|00003930| 20 5c 50 42 7b 5c 7c 47 | 7d 0a 63 6f 6e 6e 65 63 | \PB{\|G|}.connec|
|00003940| 74 65 64 20 62 79 20 6c | 69 6e 6b 69 6e 67 20 61 |ted by l|inking a|
|00003950| 6c 6c 20 72 6f 6f 74 73 | 20 6f 66 20 74 68 65 20 |ll roots| of the |
|00003960| 44 46 53 2d 66 6f 72 65 | 73 74 2e 20 49 6e 20 61 |DFS-fore|st. In a|
|00003970| 20 73 65 63 6f 6e 64 20 | 73 74 65 70 20 77 65 20 | second |step we |
|00003980| 6d 61 6b 65 0a 5c 50 42 | 7b 5c 7c 47 7d 20 62 69 |make.\PB|{\|G} bi|
|00003990| 63 6f 6e 6e 65 63 74 65 | 64 2e 0a 0a 5c 59 5c 42 |connecte|d...\Y\B|
|000039a0| 5c 34 5c 58 39 3a 61 75 | 78 69 6c 69 61 72 79 20 |\4\X9:au|xiliary |
|000039b0| 66 75 6e 63 74 69 6f 6e | 73 5c 58 24 7b 7d 5c 45 |function|s\X${}\E|
|000039c0| 7b 7d 24 5c 36 0a 5c 26 | 7b 76 6f 69 64 7d 20 5c |{}$\6.\&|{void} \|
|000039d0| 5c 7b 4d 61 6b 65 5c 5f | 62 69 63 6f 6e 6e 65 63 |\{Make\_|biconnec|
|000039e0| 74 65 64 5c 5f 67 72 61 | 70 68 7d 28 5c 26 7b 67 |ted\_gra|ph}(\&{g|
|000039f0| 72 61 70 68 7d 20 24 7b | 7d 7b 5c 41 4e 44 7d 5c |raph} ${|}{\AND}\|
|00003a00| 7c 47 29 7b 7d 24 5c 31 | 5c 31 5c 32 5c 32 5c 36 ||G){}$\1|\1\2\2\6|
|00003a10| 0a 24 7b 7d 5c 7b 7b 7d | 24 5c 31 5c 36 0a 5c 26 |.${}\{{}|$\1\6.\&|
|00003a20| 7b 6e 6f 64 65 7d 20 5c | 7c 76 3b 5c 36 0a 24 7b |{node} \||v;\6.${|
|00003a30| 7d 5c 26 7b 6e 6f 64 65 | 5c 5f 61 72 72 61 79 7d |}\&{node|\_array}|
|00003a40| 5c 6c 61 6e 67 6c 65 5c | 26 7b 62 6f 6f 6c 7d 5c |\langle\|&{bool}\|
|00003a50| 72 61 6e 67 6c 65 7b 7d | 24 20 24 7b 7d 5c 5c 7b |rangle{}|$ ${}\\{|
|00003a60| 72 65 61 63 68 65 64 7d | 28 5c 7c 47 2c 5c 33 39 |reached}|(\|G,\39|
|00003a70| 25 0a 5c 5c 7b 66 61 6c | 73 65 7d 29 3b 7b 7d 24 |%.\\{fal|se});{}$|
|00003a80| 5c 36 0a 5c 26 7b 6e 6f | 64 65 7d 20 5c 7c 75 24 |\6.\&{no|de} \|u$|
|00003a90| 7b 7d 5c 4b 5c 7c 47 2e | 5c 5c 7b 66 69 72 73 74 |{}\K\|G.|\\{first|
|00003aa0| 5c 5f 6e 6f 64 65 7d 28 | 5c 2c 29 3b 7b 7d 24 5c |\_node}(|\,);{}$\|
|00003ab0| 37 0a 5c 26 7b 66 6f 72 | 61 6c 6c 5c 5f 6e 6f 64 |7.\&{for|all\_nod|
|00003ac0| 65 73 7d 20 24 7b 7d 28 | 5c 7c 76 2c 5c 33 39 5c |es} ${}(|\|v,\39\|
|00003ad0| 7c 47 29 7b 7d 24 5c 35 | 0a 24 7b 7d 5c 7b 7b 7d ||G){}$\5|.${}\{{}|
|00003ae0| 24 5c 31 5c 36 0a 5c 26 | 7b 69 66 7d 20 24 7b 7d |$\1\6.\&|{if} ${}|
|00003af0| 28 5c 52 5c 5c 7b 72 65 | 61 63 68 65 64 7d 5b 5c |(\R\\{re|ached}[\|
|00003b00| 7c 76 5d 29 7b 7d 24 5c | 35 0a 24 7b 7d 5c 7b 7b ||v]){}$\|5.${}\{{|
|00003b10| 7d 24 5c 43 7b 20 65 78 | 70 6c 6f 72 65 20 74 68 |}$\C{ ex|plore th|
|00003b20| 65 20 63 6f 6e 6e 65 63 | 74 65 64 20 63 6f 6d 70 |e connec|ted comp|
|00003b30| 6f 6e 65 6e 74 20 77 69 | 74 68 20 72 6f 6f 74 20 |onent wi|th root |
|00003b40| 5c 50 42 7b 5c 7c 76 7d | 20 7d 5c 31 5c 36 0a 24 |\PB{\|v}| }\1\6.$|
|00003b50| 7b 7d 5c 5c 7b 44 46 53 | 7d 28 5c 7c 47 2c 5c 33 |{}\\{DFS|}(\|G,\3|
|00003b60| 39 5c 7c 76 2c 5c 33 39 | 5c 5c 7b 72 65 61 63 68 |9\|v,\39|\\{reach|
|00003b70| 65 64 7d 29 3b 7b 7d 24 | 5c 36 0a 5c 26 7b 69 66 |ed});{}$|\6.\&{if|
|00003b80| 7d 20 24 7b 7d 28 5c 7c | 75 5c 49 5c 7c 76 29 7b |} ${}(\||u\I\|v){|
|00003b90| 7d 24 5c 35 0a 24 7b 7d | 5c 7b 7b 7d 24 5c 43 7b |}$\5.${}|\{{}$\C{|
|00003ba0| 20 6c 69 6e 6b 20 5c 50 | 42 7b 5c 7c 76 7d 27 73 | link \P|B{\|v}'s|
|00003bb0| 20 63 6f 6d 70 6f 6e 65 | 6e 74 20 74 6f 20 74 68 | compone|nt to th|
|00003bc0| 65 20 66 69 72 73 74 20 | 63 6f 6d 70 6f 6e 65 6e |e first |componen|
|00003bd0| 74 20 7d 5c 31 5c 36 0a | 24 7b 7d 5c 7c 47 2e 5c |t }\1\6.|${}\|G.\|
|00003be0| 5c 7b 6e 65 77 5c 5f 65 | 64 67 65 7d 28 5c 7c 75 |\{new\_e|dge}(\|u|
|00003bf0| 2c 5c 33 39 5c 7c 76 29 | 3b 7b 7d 24 5c 36 0a 24 |,\39\|v)|;{}$\6.$|
|00003c00| 7b 7d 5c 7c 47 2e 5c 5c | 7b 6e 65 77 5c 5f 65 64 |{}\|G.\\|{new\_ed|
|00003c10| 67 65 7d 28 5c 7c 76 2c | 5c 33 39 5c 7c 75 29 3b |ge}(\|v,|\39\|u);|
|00003c20| 7b 7d 24 5c 36 0a 5c 34 | 24 7b 7d 5c 7d 7b 7d 24 |{}$\6.\4|${}\}{}$|
|00003c30| 5c 53 48 43 7b 65 6e 64 | 20 69 66 20 7d 5c 32 5c |\SHC{end| if }\2\|
|00003c40| 36 0a 5c 34 24 7b 7d 5c | 7d 7b 7d 24 5c 53 48 43 |6.\4${}\|}{}$\SHC|
|00003c50| 7b 20 65 6e 64 20 6e 6f | 74 20 72 65 61 63 68 65 |{ end no|t reache|
|00003c60| 64 20 7d 5c 32 5c 36 0a | 5c 34 24 7b 7d 5c 7d 7b |d }\2\6.|\4${}\}{|
|00003c70| 7d 24 5c 53 48 43 7b 65 | 6e 64 20 66 6f 72 61 6c |}$\SHC{e|nd foral|
|00003c80| 6c 20 7d 5c 43 7b 20 5c | 50 42 7b 5c 7c 47 7d 20 |l }\C{ \|PB{\|G} |
|00003c90| 69 73 20 6e 6f 77 20 63 | 6f 6e 6e 65 63 74 65 64 |is now c|onnected|
|00003ca0| 2e 20 57 65 20 6e 65 78 | 74 20 6d 61 6b 65 20 69 |. We nex|t make i|
|00003cb0| 74 0a 62 69 63 6f 6e 6e | 65 63 74 65 64 2e 20 7d |t.biconn|ected. }|
|00003cc0| 5c 32 5c 36 0a 5c 26 7b | 66 6f 72 61 6c 6c 5c 5f |\2\6.\&{|forall\_|
|00003cd0| 6e 6f 64 65 73 7d 20 24 | 7b 7d 28 5c 7c 76 2c 5c |nodes} $|{}(\|v,\|
|00003ce0| 33 39 5c 7c 47 29 7b 7d | 24 5c 31 5c 35 0a 24 7b |39\|G){}|$\1\5.${|
|00003cf0| 7d 5c 5c 7b 72 65 61 63 | 68 65 64 7d 5b 5c 7c 76 |}\\{reac|hed}[\|v|
|00003d00| 5d 5c 4b 5c 5c 7b 66 61 | 6c 73 65 7d 3b 7b 7d 24 |]\K\\{fa|lse};{}$|
|00003d10| 5c 32 5c 37 0a 24 7b 7d | 5c 26 7b 6e 6f 64 65 5c |\2\7.${}|\&{node\|
|00003d20| 5f 61 72 72 61 79 7d 5c | 6c 61 6e 67 6c 65 5c 26 |_array}\|langle\&|
|00003d30| 7b 69 6e 74 7d 5c 72 61 | 6e 67 6c 65 7b 7d 24 20 |{int}\ra|ngle{}$ |
|00003d40| 5c 5c 7b 64 66 73 6e 75 | 6d 7d 28 5c 7c 47 29 3b |\\{dfsnu|m}(\|G);|
|00003d50| 5c 36 0a 24 7b 7d 5c 26 | 7b 6e 6f 64 65 5c 5f 61 |\6.${}\&|{node\_a|
|00003d60| 72 72 61 79 7d 5c 6c 61 | 6e 67 6c 65 5c 26 7b 6e |rray}\la|ngle\&{n|
|00003d70| 6f 64 65 7d 5c 72 61 6e | 67 6c 65 7b 7d 24 20 24 |ode}\ran|gle{}$ $|
|00003d80| 7b 7d 5c 5c 7b 70 61 72 | 65 6e 74 7d 28 5c 7c 47 |{}\\{par|ent}(\|G|
|00003d90| 2c 5c 33 39 5c 5c 7b 6e | 69 6c 7d 29 3b 7b 7d 24 |,\39\\{n|il});{}$|
|00003da0| 5c 36 0a 5c 26 7b 69 6e | 74 7d 20 5c 5c 7b 64 66 |\6.\&{in|t} \\{df|
|00003db0| 73 5c 5f 63 6f 75 6e 74 | 7d 24 7b 7d 5c 4b 5c 54 |s\_count|}${}\K\T|
|00003dc0| 7b 30 7d 3b 7b 7d 24 5c | 36 0a 24 7b 7d 5c 26 7b |{0};{}$\|6.${}\&{|
|00003dd0| 6e 6f 64 65 5c 5f 61 72 | 72 61 79 7d 5c 6c 61 6e |node\_ar|ray}\lan|
|00003de0| 67 6c 65 5c 26 7b 69 6e | 74 7d 5c 72 61 6e 67 6c |gle\&{in|t}\rangl|
|00003df0| 65 7b 7d 24 20 5c 5c 7b | 6c 6f 77 70 74 7d 28 5c |e{}$ \\{|lowpt}(\|
|00003e00| 7c 47 29 3b 5c 37 0a 24 | 7b 7d 5c 5c 7b 64 66 73 ||G);\7.$|{}\\{dfs|
|00003e10| 5c 5f 69 6e 5c 5f 6d 61 | 6b 65 5c 5f 62 69 63 6f |\_in\_ma|ke\_bico|
|00003e20| 6e 6e 65 63 74 65 64 5c | 5f 67 72 61 70 68 7d 28 |nnected\|_graph}(|
|00003e30| 5c 7c 47 2c 5c 33 39 5c | 7c 47 2e 5c 5c 7b 66 69 |\|G,\39\||G.\\{fi|
|00003e40| 72 73 74 5c 5f 6e 6f 64 | 65 7d 28 5c 2c 29 2c 5c |rst\_nod|e}(\,),\|
|00003e50| 33 39 25 0a 5c 5c 7b 64 | 66 73 5c 5f 63 6f 75 6e |39%.\\{d|fs\_coun|
|00003e60| 74 7d 2c 5c 33 39 5c 5c | 7b 72 65 61 63 68 65 64 |t},\39\\|{reached|
|00003e70| 7d 2c 5c 33 39 5c 5c 7b | 64 66 73 6e 75 6d 7d 2c |},\39\\{|dfsnum},|
|00003e80| 5c 33 39 5c 5c 7b 6c 6f | 77 70 74 7d 2c 5c 33 39 |\39\\{lo|wpt},\39|
|00003e90| 5c 5c 7b 70 61 72 65 6e | 74 7d 29 3b 7b 7d 24 5c |\\{paren|t});{}$\|
|00003ea0| 36 0a 5c 34 24 7b 7d 5c | 7d 7b 7d 24 5c 53 48 43 |6.\4${}\|}{}$\SHC|
|00003eb0| 7b 20 65 6e 64 20 5c 50 | 42 7b 5c 5c 7b 4d 61 6b |{ end \P|B{\\{Mak|
|00003ec0| 65 5c 5f 62 69 63 6f 6e | 6e 65 63 74 65 64 5c 5f |e\_bicon|nected\_|
|00003ed0| 67 72 61 70 68 7d 7d 20 | 7d 5c 32 5c 70 61 72 0a |graph}} |}\2\par.|
|00003ee0| 5c 41 73 31 30 2c 20 31 | 35 2c 20 31 36 2c 20 31 |\As10, 1|5, 16, 1|
|00003ef0| 38 5c 45 54 73 32 37 2e | 0a 5c 55 32 2e 5c 66 69 |8\ETs27.|.\U2.\fi|
|00003f00| 0a 0a 5c 4d 7b 31 30 7d | 57 65 20 73 74 69 6c 6c |..\M{10}|We still|
|00003f10| 20 68 61 76 65 20 74 6f | 20 67 69 76 65 20 74 68 | have to| give th|
|00003f20| 65 20 70 72 6f 63 65 64 | 75 72 65 20 5c 50 42 7b |e proced|ure \PB{|
|00003f30| 5c 5c 7b 64 66 73 5c 5f | 69 6e 5c 5f 6d 61 6b 65 |\\{dfs\_|in\_make|
|00003f40| 5c 5f 62 69 63 6f 6e 6e | 65 63 74 65 64 25 0a 5c |\_biconn|ected%.\|
|00003f50| 5f 67 72 61 70 68 7d 7d | 2e 20 49 74 20 64 65 74 |_graph}}|. It det|
|00003f60| 65 72 6d 69 6e 65 73 0a | 61 72 74 69 63 75 6c 61 |ermines.|articula|
|00003f70| 74 69 6f 6e 20 70 6f 69 | 6e 74 73 20 61 6e 64 20 |tion poi|nts and |
|00003f80| 61 64 64 73 20 61 70 70 | 72 6f 70 72 69 61 74 65 |adds app|ropriate|
|00003f90| 20 65 64 67 65 73 20 77 | 68 65 6e 65 76 65 72 20 | edges w|henever |
|00003fa0| 69 74 20 64 69 73 63 6f | 76 65 72 73 20 6f 6e 65 |it disco|vers one|
|00003fb0| 2e 0a 46 6f 72 20 61 20 | 70 72 6f 6f 66 20 6f 66 |..For a |proof of|
|00003fc0| 20 63 6f 72 72 65 63 74 | 6e 65 73 73 20 77 65 20 | correct|ness we |
|00003fd0| 72 65 66 65 72 20 74 68 | 65 20 72 65 61 64 65 72 |refer th|e reader|
|00003fe0| 20 74 6f 0a 5c 63 69 74 | 65 5b 73 65 63 74 69 6f | to.\cit|e[sectio|
|00003ff0| 6e 20 49 56 2e 36 5d 7b | 4d 65 3a 62 6f 6f 6b 7d |n IV.6]{|Me:book}|
|00004000| 2e 0a 0a 5c 59 5c 42 5c | 34 5c 58 39 3a 61 75 78 |...\Y\B\|4\X9:aux|
|00004010| 69 6c 69 61 72 79 20 66 | 75 6e 63 74 69 6f 6e 73 |iliary f|unctions|
|00004020| 5c 58 24 7b 7d 5c 6d 61 | 74 68 72 65 6c 2b 5c 45 |\X${}\ma|threl+\E|
|00004030| 7b 7d 24 5c 36 0a 5c 26 | 7b 76 6f 69 64 7d 20 5c |{}$\6.\&|{void} \|
|00004040| 5c 7b 64 66 73 5c 5f 69 | 6e 5c 5f 6d 61 6b 65 5c |\{dfs\_i|n\_make\|
|00004050| 5f 62 69 63 6f 6e 6e 65 | 63 74 65 64 5c 5f 67 72 |_biconne|cted\_gr|
|00004060| 61 70 68 7d 28 5c 26 7b | 67 72 61 70 68 7d 20 24 |aph}(\&{|graph} $|
|00004070| 7b 7d 7b 5c 41 4e 44 7d | 5c 7c 47 2c 5c 33 39 7b |{}{\AND}|\|G,\39{|
|00004080| 7d 24 25 0a 5c 26 7b 6e | 6f 64 65 7d 20 5c 7c 76 |}$%.\&{n|ode} \|v|
|00004090| 24 7b 7d 2c 5c 33 39 7b | 7d 24 5c 26 7b 69 6e 74 |${},\39{|}$\&{int|
|000040a0| 7d 20 24 7b 7d 7b 5c 41 | 4e 44 7d 5c 5c 7b 64 66 |} ${}{\A|ND}\\{df|
|000040b0| 73 5c 5f 63 6f 75 6e 74 | 7d 2c 5c 33 39 5c 26 7b |s\_count|},\39\&{|
|000040c0| 6e 6f 64 65 5c 5f 61 72 | 72 61 79 7d 5c 6c 61 6e |node\_ar|ray}\lan|
|000040d0| 67 6c 65 25 0a 5c 26 7b | 62 6f 6f 6c 7d 5c 72 61 |gle%.\&{|bool}\ra|
|000040e0| 6e 67 6c 65 7b 7d 24 20 | 24 7b 7d 7b 5c 41 4e 44 |ngle{}$ |${}{\AND|
|000040f0| 7d 5c 5c 7b 72 65 61 63 | 68 65 64 7d 2c 5c 33 7b |}\\{reac|hed},\3{|
|00004100| 2d 31 7d 5c 33 39 5c 26 | 7b 6e 6f 64 65 5c 5f 61 |-1}\39\&|{node\_a|
|00004110| 72 72 61 79 7d 5c 6c 61 | 6e 67 6c 65 5c 26 7b 69 |rray}\la|ngle\&{i|
|00004120| 6e 74 7d 25 0a 5c 72 61 | 6e 67 6c 65 7b 7d 24 20 |nt}%.\ra|ngle{}$ |
|00004130| 24 7b 7d 7b 5c 41 4e 44 | 7d 5c 5c 7b 64 66 73 6e |${}{\AND|}\\{dfsn|
|00004140| 75 6d 7d 2c 5c 33 39 5c | 26 7b 6e 6f 64 65 5c 5f |um},\39\|&{node\_|
|00004150| 61 72 72 61 79 7d 5c 6c | 61 6e 67 6c 65 5c 26 7b |array}\l|angle\&{|
|00004160| 69 6e 74 7d 5c 72 61 6e | 67 6c 65 7b 7d 24 20 24 |int}\ran|gle{}$ $|
|00004170| 7b 7d 7b 25 0a 5c 41 4e | 44 7d 5c 5c 7b 6c 6f 77 |{}{%.\AN|D}\\{low|
|00004180| 70 74 7d 2c 5c 33 39 5c | 26 7b 6e 6f 64 65 5c 5f |pt},\39\|&{node\_|
|00004190| 61 72 72 61 79 7d 5c 6c | 61 6e 67 6c 65 5c 26 7b |array}\l|angle\&{|
|000041a0| 6e 6f 64 65 7d 5c 72 61 | 6e 67 6c 65 7b 7d 24 20 |node}\ra|ngle{}$ |
|000041b0| 24 7b 7d 7b 5c 41 4e 44 | 7d 25 0a 5c 5c 7b 70 61 |${}{\AND|}%.\\{pa|
|000041c0| 72 65 6e 74 7d 29 7b 7d | 24 5c 31 5c 31 5c 32 5c |rent}){}|$\1\1\2\|
|000041d0| 32 5c 36 0a 24 7b 7d 5c | 7b 7b 7d 24 5c 31 5c 36 |2\6.${}\|{{}$\1\6|
|000041e0| 0a 5c 26 7b 6e 6f 64 65 | 7d 20 5c 7c 77 3b 5c 36 |.\&{node|} \|w;\6|
|000041f0| 0a 5c 26 7b 65 64 67 65 | 7d 20 5c 7c 65 3b 5c 37 |.\&{edge|} \|e;\7|
|00004200| 0a 24 7b 7d 5c 5c 7b 64 | 66 73 6e 75 6d 7d 5b 5c |.${}\\{d|fsnum}[\|
|00004210| 7c 76 5d 5c 4b 5c 5c 7b | 64 66 73 5c 5f 63 6f 75 ||v]\K\\{|dfs\_cou|
|00004220| 6e 74 7d 5c 50 50 3b 7b | 7d 24 5c 36 0a 24 7b 7d |nt}\PP;{|}$\6.${}|
|00004230| 5c 5c 7b 6c 6f 77 70 74 | 7d 5b 5c 7c 76 5d 5c 4b |\\{lowpt|}[\|v]\K|
|00004240| 5c 5c 7b 64 66 73 6e 75 | 6d 7d 5b 5c 7c 76 5d 3b |\\{dfsnu|m}[\|v];|
|00004250| 7b 7d 24 5c 36 0a 24 7b | 7d 5c 5c 7b 72 65 61 63 |{}$\6.${|}\\{reac|
|00004260| 68 65 64 7d 5b 5c 7c 76 | 5d 5c 4b 5c 5c 7b 74 72 |hed}[\|v|]\K\\{tr|
|00004270| 75 65 7d 3b 7b 7d 24 5c | 36 0a 5c 26 7b 69 66 7d |ue};{}$\|6.\&{if}|
|00004280| 20 24 7b 7d 28 5c 52 5c | 7c 47 2e 5c 5c 7b 66 69 | ${}(\R\||G.\\{fi|
|00004290| 72 73 74 5c 5f 61 64 6a | 5c 5f 65 64 67 65 7d 28 |rst\_adj|\_edge}(|
|000042a0| 5c 7c 76 29 29 7b 7d 24 | 5c 31 5c 35 0a 5c 26 7b |\|v)){}$|\1\5.\&{|
|000042b0| 72 65 74 75 72 6e 7d 3b | 5c 53 48 43 7b 6e 6f 20 |return};|\SHC{no |
|000042c0| 63 68 69 6c 64 72 65 6e | 20 7d 5c 32 5c 37 0a 5c |children| }\2\7.\|
|000042d0| 26 7b 6e 6f 64 65 7d 20 | 5c 7c 75 24 7b 7d 5c 4b |&{node} |\|u${}\K|
|000042e0| 5c 5c 7b 74 61 72 67 65 | 74 7d 28 5c 7c 47 2e 5c |\\{targe|t}(\|G.\|
|000042f0| 5c 7b 66 69 72 73 74 5c | 5f 61 64 6a 5c 5f 65 64 |\{first\|_adj\_ed|
|00004300| 67 65 7d 28 5c 7c 76 29 | 29 7b 7d 24 3b 5c 53 48 |ge}(\|v)|){}$;\SH|
|00004310| 43 7b 66 69 72 73 74 20 | 63 68 69 6c 64 0a 7d 5c |C{first |child.}\|
|00004320| 37 0a 5c 26 7b 66 6f 72 | 61 6c 6c 5c 5f 61 64 6a |7.\&{for|all\_adj|
|00004330| 5c 5f 65 64 67 65 73 7d | 20 24 7b 7d 28 5c 7c 65 |\_edges}| ${}(\|e|
|00004340| 2c 5c 33 39 5c 7c 76 29 | 7b 7d 24 5c 35 0a 24 7b |,\39\|v)|{}$\5.${|
|00004350| 7d 5c 7b 7b 7d 24 5c 31 | 5c 36 0a 24 7b 7d 5c 7c |}\{{}$\1|\6.${}\||
|00004360| 77 5c 4b 5c 5c 7b 74 61 | 72 67 65 74 7d 28 5c 7c |w\K\\{ta|rget}(\||
|00004370| 65 29 3b 7b 7d 24 5c 36 | 0a 5c 26 7b 69 66 7d 20 |e);{}$\6|.\&{if} |
|00004380| 24 7b 7d 28 5c 52 5c 5c | 7b 72 65 61 63 68 65 64 |${}(\R\\|{reached|
|00004390| 7d 5b 5c 7c 77 5d 29 7b | 7d 24 5c 35 0a 24 7b 7d |}[\|w]){|}$\5.${}|
|000043a0| 5c 7b 7b 7d 24 5c 43 7b | 20 65 20 69 73 20 61 20 |\{{}$\C{| e is a |
|000043b0| 74 72 65 65 20 65 64 67 | 65 20 7d 5c 31 5c 36 0a |tree edg|e }\1\6.|
|000043c0| 24 7b 7d 5c 5c 7b 70 61 | 72 65 6e 74 7d 5b 5c 7c |${}\\{pa|rent}[\||
|000043d0| 77 5d 5c 4b 5c 7c 76 3b | 7b 7d 24 5c 36 0a 24 7b |w]\K\|v;|{}$\6.${|
|000043e0| 7d 5c 5c 7b 64 66 73 5c | 5f 69 6e 5c 5f 6d 61 6b |}\\{dfs\|_in\_mak|
|000043f0| 65 5c 5f 62 69 63 6f 6e | 6e 65 63 74 65 64 5c 5f |e\_bicon|nected\_|
|00004400| 67 72 61 70 68 7d 28 5c | 7c 47 2c 5c 33 39 5c 7c |graph}(\||G,\39\||
|00004410| 77 2c 5c 33 39 5c 5c 7b | 64 66 73 5c 5f 63 6f 75 |w,\39\\{|dfs\_cou|
|00004420| 6e 74 7d 2c 5c 33 39 25 | 0a 5c 5c 7b 72 65 61 63 |nt},\39%|.\\{reac|
|00004430| 68 65 64 7d 2c 5c 33 39 | 5c 5c 7b 64 66 73 6e 75 |hed},\39|\\{dfsnu|
|00004440| 6d 7d 2c 5c 33 39 5c 5c | 7b 6c 6f 77 70 74 7d 2c |m},\39\\|{lowpt},|
|00004450| 5c 33 39 5c 5c 7b 70 61 | 72 65 6e 74 7d 29 3b 7b |\39\\{pa|rent});{|
|00004460| 7d 24 5c 36 0a 5c 26 7b | 69 66 7d 20 24 7b 7d 28 |}$\6.\&{|if} ${}(|
|00004470| 5c 5c 7b 6c 6f 77 70 74 | 7d 5b 5c 7c 77 5d 5c 45 |\\{lowpt|}[\|w]\E|
|00004480| 5c 5c 7b 64 66 73 6e 75 | 6d 7d 5b 5c 7c 76 5d 29 |\\{dfsnu|m}[\|v])|
|00004490| 7b 7d 24 5c 35 0a 24 7b | 7d 5c 7b 7b 7d 24 5c 43 |{}$\5.${|}\{{}$\C|
|000044a0| 7b 20 5c 50 42 7b 5c 7c | 76 7d 20 69 73 20 61 6e |{ \PB{\||v} is an|
|000044b0| 20 61 72 74 69 63 75 6c | 61 74 69 6f 6e 20 70 6f | articul|ation po|
|000044c0| 69 6e 74 2e 20 57 65 20 | 6e 6f 77 20 61 64 64 20 |int. We |now add |
|000044d0| 61 6e 20 65 64 67 65 2e | 20 49 66 20 5c 50 42 7b |an edge.| If \PB{|
|000044e0| 5c 7c 77 7d 0a 69 73 20 | 74 68 65 20 66 69 72 73 |\|w}.is |the firs|
|000044f0| 74 20 63 68 69 6c 64 20 | 61 6e 64 20 5c 50 42 7b |t child |and \PB{|
|00004500| 5c 7c 76 7d 20 68 61 73 | 20 61 20 70 61 72 65 6e |\|v} has| a paren|
|00004510| 74 20 74 68 65 6e 20 77 | 65 20 63 6f 6e 6e 65 63 |t then w|e connec|
|00004520| 74 20 5c 50 42 7b 5c 7c | 77 7d 20 61 6e 64 20 5c |t \PB{\||w} and \|
|00004530| 50 42 7b 25 0a 5c 5c 7b | 70 61 72 65 6e 74 7d 5b |PB{%.\\{|parent}[|
|00004540| 5c 7c 76 5d 7d 2c 20 69 | 66 20 5c 50 42 7b 5c 7c |\|v]}, i|f \PB{\||
|00004550| 77 7d 20 69 73 20 61 20 | 66 69 72 73 74 20 63 68 |w} is a |first ch|
|00004560| 69 6c 64 20 61 6e 64 20 | 5c 50 42 7b 5c 7c 76 7d |ild and |\PB{\|v}|
|00004570| 20 68 61 73 20 6e 6f 20 | 70 61 72 65 6e 74 20 74 | has no |parent t|
|00004580| 68 65 6e 0a 77 65 20 64 | 6f 20 6e 6f 74 68 69 6e |hen.we d|o nothin|
|00004590| 67 2e 20 49 66 20 5c 50 | 42 7b 5c 7c 77 7d 20 69 |g. If \P|B{\|w} i|
|000045a0| 73 20 6e 6f 74 20 74 68 | 65 20 66 69 72 73 74 20 |s not th|e first |
|000045b0| 63 68 69 6c 64 20 74 68 | 65 6e 20 77 65 20 63 6f |child th|en we co|
|000045c0| 6e 6e 65 63 74 20 5c 50 | 42 7b 5c 7c 77 7d 20 74 |nnect \P|B{\|w} t|
|000045d0| 6f 0a 74 68 65 20 66 69 | 72 73 74 20 63 68 69 6c |o.the fi|rst chil|
|000045e0| 64 2e 20 54 68 65 20 6e | 65 74 20 65 66 66 65 63 |d. The n|et effec|
|000045f0| 74 20 6f 66 20 61 6c 6c | 20 6f 66 20 74 68 69 73 |t of all| of this|
|00004600| 20 69 73 20 74 6f 20 6c | 69 6e 6b 20 61 6c 6c 20 | is to l|ink all |
|00004610| 63 68 69 6c 64 72 65 6e | 20 6f 66 20 61 6e 0a 61 |children| of an.a|
|00004620| 72 74 69 63 75 6c 61 74 | 69 6f 6e 20 70 6f 69 6e |rticulat|ion poin|
|00004630| 74 20 74 6f 20 74 68 65 | 20 66 69 72 73 74 20 63 |t to the| first c|
|00004640| 68 69 6c 64 20 61 6e 64 | 20 74 68 65 20 66 69 72 |hild and| the fir|
|00004650| 73 74 20 63 68 69 6c 64 | 20 74 6f 20 74 68 65 20 |st child| to the |
|00004660| 70 61 72 65 6e 74 20 28 | 69 66 20 69 74 0a 65 78 |parent (|if it.ex|
|00004670| 69 73 74 73 29 20 7d 5c | 31 5c 36 0a 5c 26 7b 69 |ists) }\|1\6.\&{i|
|00004680| 66 7d 20 24 7b 7d 28 5c | 7c 77 5c 45 5c 7c 75 5c |f} ${}(\||w\E\|u\|
|00004690| 57 5c 5c 7b 70 61 72 65 | 6e 74 7d 5b 5c 7c 76 5d |W\\{pare|nt}[\|v]|
|000046a0| 29 7b 7d 24 5c 35 0a 24 | 7b 7d 5c 7b 7b 7d 24 5c |){}$\5.$|{}\{{}$\|
|000046b0| 31 5c 36 0a 24 7b 7d 5c | 7c 47 2e 5c 5c 7b 6e 65 |1\6.${}\||G.\\{ne|
|000046c0| 77 5c 5f 65 64 67 65 7d | 28 5c 7c 77 2c 5c 33 39 |w\_edge}|(\|w,\39|
|000046d0| 5c 5c 7b 70 61 72 65 6e | 74 7d 5b 5c 7c 76 5d 29 |\\{paren|t}[\|v])|
|000046e0| 3b 7b 7d 24 5c 36 0a 24 | 7b 7d 5c 7c 47 2e 5c 5c |;{}$\6.$|{}\|G.\\|
|000046f0| 7b 6e 65 77 5c 5f 65 64 | 67 65 7d 28 5c 5c 7b 70 |{new\_ed|ge}(\\{p|
|00004700| 61 72 65 6e 74 7d 5b 5c | 7c 76 5d 2c 5c 33 39 5c |arent}[\||v],\39\|
|00004710| 7c 77 29 3b 7b 7d 24 5c | 36 0a 5c 34 24 7b 7d 5c ||w);{}$\|6.\4${}\|
|00004720| 7d 7b 7d 24 5c 32 5c 36 | 0a 5c 26 7b 69 66 7d 20 |}{}$\2\6|.\&{if} |
|00004730| 24 7b 7d 28 5c 7c 77 5c | 49 5c 7c 75 29 7b 7d 24 |${}(\|w\|I\|u){}$|
|00004740| 5c 35 0a 24 7b 7d 5c 7b | 7b 7d 24 5c 31 5c 36 0a |\5.${}\{|{}$\1\6.|
|00004750| 24 7b 7d 5c 7c 47 2e 5c | 5c 7b 6e 65 77 5c 5f 65 |${}\|G.\|\{new\_e|
|00004760| 64 67 65 7d 28 5c 7c 75 | 2c 5c 33 39 5c 7c 77 29 |dge}(\|u|,\39\|w)|
|00004770| 3b 7b 7d 24 5c 36 0a 24 | 7b 7d 5c 7c 47 2e 5c 5c |;{}$\6.$|{}\|G.\\|
|00004780| 7b 6e 65 77 5c 5f 65 64 | 67 65 7d 28 5c 7c 77 2c |{new\_ed|ge}(\|w,|
|00004790| 5c 33 39 5c 7c 75 29 3b | 7b 7d 24 5c 36 0a 5c 34 |\39\|u);|{}$\6.\4|
|000047a0| 24 7b 7d 5c 7d 7b 7d 24 | 5c 32 5c 36 0a 5c 34 24 |${}\}{}$|\2\6.\4$|
|000047b0| 7b 7d 5c 7d 7b 7d 24 5c | 53 48 43 7b 20 65 6e 64 |{}\}{}$\|SHC{ end|
|000047c0| 20 69 66 20 6c 6f 77 70 | 74 20 3d 20 64 66 73 6e | if lowp|t = dfsn|
|000047d0| 75 6d 20 7d 5c 32 5c 36 | 0a 24 7b 7d 5c 5c 7b 6c |um }\2\6|.${}\\{l|
|000047e0| 6f 77 70 74 7d 5b 5c 7c | 76 5d 5c 4b 5c 5c 7b 4d |owpt}[\||v]\K\\{M|
|000047f0| 69 6e 7d 28 5c 5c 7b 6c | 6f 77 70 74 7d 5b 5c 7c |in}(\\{l|owpt}[\||
|00004800| 76 5d 2c 5c 33 39 5c 5c | 7b 6c 6f 77 70 74 7d 5b |v],\39\\|{lowpt}[|
|00004810| 5c 7c 77 5d 29 3b 7b 7d | 24 5c 36 0a 5c 34 24 7b |\|w]);{}|$\6.\4${|
|00004820| 7d 5c 7d 7b 7d 24 5c 53 | 48 43 7b 65 6e 64 20 74 |}\}{}$\S|HC{end t|
|00004830| 72 65 65 20 65 64 67 65 | 20 7d 5c 32 5c 36 0a 5c |ree edge| }\2\6.\|
|00004840| 26 7b 65 6c 73 65 7d 5c | 31 5c 35 0a 24 7b 7d 5c |&{else}\|1\5.${}\|
|00004850| 5c 7b 6c 6f 77 70 74 7d | 5b 5c 7c 76 5d 5c 4b 5c |\{lowpt}|[\|v]\K\|
|00004860| 5c 7b 4d 69 6e 7d 28 5c | 5c 7b 6c 6f 77 70 74 7d |\{Min}(\|\{lowpt}|
|00004870| 5b 5c 7c 76 5d 2c 5c 33 | 39 5c 5c 7b 64 66 73 6e |[\|v],\3|9\\{dfsn|
|00004880| 75 6d 7d 5b 5c 7c 77 5d | 29 7b 7d 24 3b 5c 53 48 |um}[\|w]|){}$;\SH|
|00004890| 43 7b 6e 6f 6e 20 74 72 | 65 65 0a 65 64 67 65 20 |C{non tr|ee.edge |
|000048a0| 7d 5c 32 5c 36 0a 5c 34 | 24 7b 7d 5c 7d 7b 7d 24 |}\2\6.\4|${}\}{}$|
|000048b0| 5c 53 48 43 7b 20 65 6e | 64 20 66 6f 72 61 6c 6c |\SHC{ en|d forall|
|000048c0| 20 7d 5c 32 5c 36 0a 5c | 34 24 7b 7d 5c 7d 7b 7d | }\2\6.\|4${}\}{}|
|000048d0| 24 5c 53 48 43 7b 65 6e | 64 20 64 66 73 20 7d 5c |$\SHC{en|d dfs }\|
|000048e0| 32 5c 70 61 72 0a 5c 66 | 69 0a 0a 5c 4d 7b 31 31 |2\par.\f|i..\M{11|
|000048f0| 7d 42 65 63 61 75 73 65 | 20 77 65 20 75 73 65 20 |}Because| we use |
|00004900| 74 68 65 20 66 75 6e 63 | 74 69 6f 6e 20 5c 50 42 |the func|tion \PB|
|00004910| 7b 5c 5c 7b 64 66 73 5c | 5f 69 6e 5c 5f 6d 61 6b |{\\{dfs\|_in\_mak|
|00004920| 65 5c 5f 62 69 63 6f 6e | 6e 65 63 74 65 64 5c 5f |e\_bicon|nected\_|
|00004930| 67 72 61 70 68 7d 7d 0a | 62 65 66 6f 72 65 20 69 |graph}}.|before i|
|00004940| 74 73 20 64 65 63 6c 61 | 72 61 74 69 6f 6e 2c 0a |ts decla|ration,.|
|00004950| 6c 65 74 27 73 20 61 64 | 64 20 69 74 20 74 6f 20 |let's ad|d it to |
|00004960| 74 68 65 20 67 6c 6f 62 | 61 6c 20 64 65 63 6c 61 |the glob|al decla|
|00004970| 72 61 74 69 6f 6e 73 2e | 0a 0a 5c 59 5c 42 5c 34 |rations.|..\Y\B\4|
|00004980| 5c 58 31 31 3a 74 79 70 | 65 64 65 66 73 2c 20 67 |\X11:typ|edefs, g|
|00004990| 6c 6f 62 61 6c 20 76 61 | 72 69 61 62 6c 65 73 20 |lobal va|riables |
|000049a0| 61 6e 64 20 63 6c 61 73 | 73 20 64 65 63 6c 61 72 |and clas|s declar|
|000049b0| 61 74 69 6f 6e 73 5c 58 | 24 7b 7d 5c 45 7b 7d 24 |ations\X|${}\E{}$|
|000049c0| 5c 36 0a 5c 26 7b 76 6f | 69 64 7d 20 5c 5c 7b 64 |\6.\&{vo|id} \\{d|
|000049d0| 66 73 5c 5f 69 6e 5c 5f | 6d 61 6b 65 5c 5f 62 69 |fs\_in\_|make\_bi|
|000049e0| 63 6f 6e 6e 65 63 74 65 | 64 5c 5f 67 72 61 70 68 |connecte|d\_graph|
|000049f0| 7d 28 5c 26 7b 67 72 61 | 70 68 7d 20 24 7b 7d 7b |}(\&{gra|ph} ${}{|
|00004a00| 5c 41 4e 44 7d 5c 7c 47 | 2c 5c 33 39 7b 7d 24 25 |\AND}\|G|,\39{}$%|
|00004a10| 0a 5c 26 7b 6e 6f 64 65 | 7d 20 5c 7c 76 24 7b 7d |.\&{node|} \|v${}|
|00004a20| 2c 5c 33 39 7b 7d 24 5c | 26 7b 69 6e 74 7d 20 24 |,\39{}$\|&{int} $|
|00004a30| 7b 7d 7b 5c 41 4e 44 7d | 5c 5c 7b 64 66 73 5c 5f |{}{\AND}|\\{dfs\_|
|00004a40| 63 6f 75 6e 74 7d 2c 5c | 33 39 5c 26 7b 6e 6f 64 |count},\|39\&{nod|
|00004a50| 65 5c 5f 61 72 72 61 79 | 7d 5c 6c 61 6e 67 6c 65 |e\_array|}\langle|
|00004a60| 25 0a 5c 26 7b 62 6f 6f | 6c 7d 5c 72 61 6e 67 6c |%.\&{boo|l}\rangl|
|00004a70| 65 7b 7d 24 20 24 7b 7d | 7b 5c 41 4e 44 7d 5c 5c |e{}$ ${}|{\AND}\\|
|00004a80| 7b 72 65 61 63 68 65 64 | 7d 2c 5c 33 7b 2d 31 7d |{reached|},\3{-1}|
|00004a90| 5c 33 39 5c 26 7b 6e 6f | 64 65 5c 5f 61 72 72 61 |\39\&{no|de\_arra|
|00004aa0| 79 7d 5c 6c 61 6e 67 6c | 65 5c 26 7b 69 6e 74 7d |y}\langl|e\&{int}|
|00004ab0| 25 0a 5c 72 61 6e 67 6c | 65 7b 7d 24 20 24 7b 7d |%.\rangl|e{}$ ${}|
|00004ac0| 7b 5c 41 4e 44 7d 5c 5c | 7b 64 66 73 6e 75 6d 7d |{\AND}\\|{dfsnum}|
|00004ad0| 2c 5c 33 39 5c 26 7b 6e | 6f 64 65 5c 5f 61 72 72 |,\39\&{n|ode\_arr|
|00004ae0| 61 79 7d 5c 6c 61 6e 67 | 6c 65 5c 26 7b 69 6e 74 |ay}\lang|le\&{int|
|00004af0| 7d 5c 72 61 6e 67 6c 65 | 7b 7d 24 20 24 7b 7d 7b |}\rangle|{}$ ${}{|
|00004b00| 25 0a 5c 41 4e 44 7d 5c | 5c 7b 6c 6f 77 70 74 7d |%.\AND}\|\{lowpt}|
|00004b10| 2c 5c 33 39 5c 26 7b 6e | 6f 64 65 5c 5f 61 72 72 |,\39\&{n|ode\_arr|
|00004b20| 61 79 7d 5c 6c 61 6e 67 | 6c 65 5c 26 7b 6e 6f 64 |ay}\lang|le\&{nod|
|00004b30| 65 7d 5c 72 61 6e 67 6c | 65 7b 7d 24 20 24 7b 7d |e}\rangl|e{}$ ${}|
|00004b40| 7b 5c 41 4e 44 7d 25 0a | 5c 5c 7b 70 61 72 65 6e |{\AND}%.|\\{paren|
|00004b50| 74 7d 29 7b 7d 24 3b 5c | 70 61 72 0a 5c 41 73 31 |t}){}$;\|par.\As1|
|00004b60| 34 2c 20 31 37 5c 45 54 | 73 32 30 2e 0a 5c 55 32 |4, 17\ET|s20..\U2|
|00004b70| 2e 5c 66 69 0a 0a 5c 4d | 7b 31 32 7d 57 65 20 6d |.\fi..\M|{12}We m|
|00004b80| 61 6b 65 20 5c 50 42 7b | 5c 7c 48 7d 20 61 20 63 |ake \PB{|\|H} a c|
|00004b90| 6f 70 79 20 6f 66 20 5c | 50 42 7b 5c 7c 47 7d 20 |opy of \|PB{\|G} |
|00004ba0| 61 6e 64 20 63 72 65 61 | 74 65 20 62 69 64 69 72 |and crea|te bidir|
|00004bb0| 65 63 74 69 6f 6e 61 6c | 20 6c 69 6e 6b 73 0a 62 |ectional| links.b|
|00004bc0| 65 74 77 65 65 6e 20 74 | 68 65 0a 76 65 72 74 69 |etween t|he.verti|
|00004bd0| 63 65 73 20 61 6e 64 20 | 65 64 67 65 73 20 6f 66 |ces and |edges of|
|00004be0| 20 5c 50 42 7b 5c 7c 47 | 7d 20 61 6e 64 20 5c 50 | \PB{\|G|} and \P|
|00004bf0| 42 7b 5c 7c 48 7d 2e 0a | 41 6c 73 6f 2c 20 65 61 |B{\|H}..|Also, ea|
|00004c00| 63 68 20 65 64 67 65 20 | 69 6e 20 5c 50 42 7b 5c |ch edge |in \PB{\|
|00004c10| 5c 7b 47 69 6e 7d 7d 20 | 67 65 74 73 20 61 20 6c |\{Gin}} |gets a l|
|00004c20| 69 6e 6b 20 74 6f 20 69 | 74 73 20 63 6f 70 79 20 |ink to i|ts copy |
|00004c30| 69 6e 20 5c 50 42 7b 5c | 7c 48 7d 20 61 6e 64 20 |in \PB{\||H} and |
|00004c40| 65 76 65 72 79 0a 65 64 | 67 65 0a 6f 66 20 5c 50 |every.ed|ge.of \P|
|00004c50| 42 7b 5c 7c 48 7d 20 67 | 65 74 73 20 74 6f 20 6b |B{\|H} g|ets to k|
|00004c60| 6e 6f 77 20 69 74 73 20 | 72 65 76 65 72 73 61 6c |now its |reversal|
|00004c70| 2e 20 4d 6f 72 65 20 70 | 72 65 63 69 73 65 6c 79 |. More p|recisely|
|00004c80| 2c 20 5c 50 42 7b 24 5c | 7c 48 5b 5c 7c 47 5b 5c |, \PB{$\||H[\|G[\|
|00004c90| 7c 76 5d 5d 5c 4b 25 0a | 5c 7c 76 24 7d 20 66 6f ||v]]\K%.|\|v$} fo|
|00004ca0| 72 20 65 76 65 72 79 0a | 6e 6f 64 65 20 5c 50 42 |r every.|node \PB|
|00004cb0| 7b 5c 7c 76 7d 20 6f 66 | 20 5c 50 42 7b 5c 7c 47 |{\|v} of| \PB{\|G|
|00004cc0| 7d 20 61 6e 64 20 5c 50 | 42 7b 24 5c 7c 48 5b 5c |} and \P|B{$\|H[\|
|00004cd0| 7c 47 5b 5c 7c 65 5d 5d | 5c 4b 5c 7c 65 24 7d 20 ||G[\|e]]|\K\|e$} |
|00004ce0| 66 6f 72 20 65 76 65 72 | 79 20 65 64 67 65 20 5c |for ever|y edge \|
|00004cf0| 50 42 7b 5c 7c 65 7d 0a | 6f 66 20 5c 50 42 7b 5c |PB{\|e}.|of \PB{\|
|00004d00| 7c 47 7d 2c 20 61 6e 64 | 0a 5c 50 42 7b 5c 5c 7b ||G}, and|.\PB{\\{|
|00004d10| 63 6f 6d 70 61 6e 69 6f | 6e 5c 5f 69 6e 5c 5f 48 |companio|n\_in\_H|
|00004d20| 7d 5b 5c 5c 7b 65 69 6e | 7d 5d 7d 20 69 73 20 74 |}[\\{ein|}]} is t|
|00004d30| 68 65 20 65 64 67 65 20 | 69 6e 20 5c 50 42 7b 5c |he edge |in \PB{\|
|00004d40| 7c 48 7d 20 63 6f 72 72 | 65 73 70 6f 6e 64 69 6e ||H} corr|espondin|
|00004d50| 67 20 74 6f 20 74 68 65 | 0a 65 64 67 65 0a 5c 50 |g to the|.edge.\P|
|00004d60| 42 7b 5c 5c 7b 65 69 6e | 7d 7d 20 6f 66 20 5c 50 |B{\\{ein|}} of \P|
|00004d70| 42 7b 5c 5c 7b 47 69 6e | 7d 7d 20 66 6f 72 20 65 |B{\\{Gin|}} for e|
|00004d80| 76 65 72 79 20 65 64 67 | 65 20 5c 50 42 7b 5c 5c |very edg|e \PB{\\|
|00004d90| 7b 65 69 6e 7d 7d 20 6f | 66 20 5c 50 42 7b 5c 5c |{ein}} o|f \PB{\\|
|00004da0| 7b 47 69 6e 7d 7d 2e 0a | 46 69 6e 61 6c 6c 79 2c |{Gin}}..|Finally,|
|00004db0| 20 69 66 20 5c 50 42 7b | 24 5c 7c 65 5c 4b 28 5c | if \PB{|$\|e\K(\|
|00004dc0| 7c 75 2c 5c 7c 76 29 24 | 7d 20 69 73 0a 61 6e 20 ||u,\|v)$|} is.an |
|00004dd0| 65 64 67 65 20 6f 66 20 | 5c 50 42 7b 5c 7c 48 7d |edge of |\PB{\|H}|
|00004de0| 20 74 68 65 6e 20 5c 50 | 42 7b 24 5c 5c 7b 72 65 | then \P|B{$\\{re|
|00004df0| 76 65 72 73 61 6c 7d 5b | 5c 7c 65 5d 5c 4b 28 5c |versal}[|\|e]\K(\|
|00004e00| 7c 76 2c 5c 7c 75 29 24 | 7d 2e 0a 0a 0a 0a 5c 59 ||v,\|u)$|}.....\Y|
|00004e10| 5c 42 5c 34 5c 58 31 32 | 3a 6d 61 6b 65 20 5c 50 |\B\4\X12|:make \P|
|00004e20| 42 7b 5c 7c 48 7d 20 61 | 20 63 6f 70 79 20 6f 66 |B{\|H} a| copy of|
|00004e30| 20 5c 50 42 7b 5c 7c 47 | 7d 5c 58 24 7b 7d 5c 45 | \PB{\|G|}\X${}\E|
|00004e40| 7b 7d 24 5c 36 0a 24 5c | 26 7b 47 52 41 50 48 7d |{}$\6.$\|&{GRAPH}|
|00004e50| 5c 6c 61 6e 67 6c 65 5c | 26 7b 6e 6f 64 65 7d 2c |\langle\|&{node},|
|00004e60| 5c 33 39 5c 26 7b 65 64 | 67 65 7d 5c 72 61 6e 67 |\39\&{ed|ge}\rang|
|00004e70| 6c 65 7b 7d 24 20 5c 7c | 48 3b 5c 36 0a 24 7b 7d |le{}$ \||H;\6.${}|
|00004e80| 5c 26 7b 65 64 67 65 5c | 5f 61 72 72 61 79 7d 5c |\&{edge\|_array}\|
|00004e90| 6c 61 6e 67 6c 65 5c 26 | 7b 65 64 67 65 7d 5c 72 |langle\&|{edge}\r|
|00004ea0| 61 6e 67 6c 65 7b 7d 24 | 20 5c 5c 7b 63 6f 6d 70 |angle{}$| \\{comp|
|00004eb0| 61 6e 69 6f 6e 5c 5f 69 | 6e 5c 5f 48 7d 28 5c 5c |anion\_i|n\_H}(\\|
|00004ec0| 7b 47 69 6e 7d 29 3b 5c | 37 0a 24 7b 7d 5c 7b 7b |{Gin});\|7.${}\{{|
|00004ed0| 7d 24 5c 31 5c 36 0a 5c | 26 7b 6e 6f 64 65 7d 20 |}$\1\6.\|&{node} |
|00004ee0| 5c 7c 76 3b 5c 37 0a 5c | 26 7b 66 6f 72 61 6c 6c |\|v;\7.\|&{forall|
|00004ef0| 5c 5f 6e 6f 64 65 73 7d | 20 24 7b 7d 28 5c 7c 76 |\_nodes}| ${}(\|v|
|00004f00| 2c 5c 33 39 5c 7c 47 29 | 7b 7d 24 5c 31 5c 35 0a |,\39\|G)|{}$\1\5.|
|00004f10| 24 7b 7d 5c 7c 47 2e 5c | 5c 7b 61 73 73 69 67 6e |${}\|G.\|\{assign|
|00004f20| 7d 28 5c 7c 76 2c 5c 33 | 39 5c 7c 48 2e 5c 5c 7b |}(\|v,\3|9\|H.\\{|
|00004f30| 6e 65 77 5c 5f 6e 6f 64 | 65 7d 28 5c 7c 76 29 29 |new\_nod|e}(\|v))|
|00004f40| 3b 7b 7d 24 5c 32 5c 37 | 0a 5c 26 7b 65 64 67 65 |;{}$\2\7|.\&{edge|
|00004f50| 7d 20 5c 7c 65 3b 5c 37 | 0a 5c 26 7b 66 6f 72 61 |} \|e;\7|.\&{fora|
|00004f60| 6c 6c 5c 5f 65 64 67 65 | 73 7d 20 24 7b 7d 28 5c |ll\_edge|s} ${}(\|
|00004f70| 7c 65 2c 5c 33 39 5c 7c | 47 29 7b 7d 24 5c 31 5c ||e,\39\||G){}$\1\|
|00004f80| 35 0a 24 7b 7d 5c 7c 47 | 2e 5c 5c 7b 61 73 73 69 |5.${}\|G|.\\{assi|
|00004f90| 67 6e 7d 28 5c 7c 65 2c | 5c 33 39 5c 7c 48 2e 5c |gn}(\|e,|\39\|H.\|
|00004fa0| 5c 7b 6e 65 77 5c 5f 65 | 64 67 65 7d 28 5c 7c 47 |\{new\_e|dge}(\|G|
|00004fb0| 5b 5c 5c 7b 73 6f 75 72 | 63 65 7d 28 5c 7c 65 29 |[\\{sour|ce}(\|e)|
|00004fc0| 5d 2c 5c 33 39 5c 7c 47 | 5b 25 0a 5c 5c 7b 74 61 |],\39\|G|[%.\\{ta|
|00004fd0| 72 67 65 74 7d 28 5c 7c | 65 29 5d 2c 5c 33 39 5c |rget}(\||e)],\39\|
|00004fe0| 7c 65 29 29 3b 7b 7d 24 | 5c 32 5c 37 0a 5c 26 7b ||e));{}$|\2\7.\&{|
|00004ff0| 65 64 67 65 7d 20 5c 5c | 7b 65 69 6e 7d 3b 5c 37 |edge} \\|{ein};\7|
|00005000| 0a 5c 26 7b 66 6f 72 61 | 6c 6c 5c 5f 65 64 67 65 |.\&{fora|ll\_edge|
|00005010| 73 7d 20 24 7b 7d 28 5c | 5c 7b 65 69 6e 7d 2c 5c |s} ${}(\|\{ein},\|
|00005020| 33 39 5c 5c 7b 47 69 6e | 7d 29 7b 7d 24 5c 31 5c |39\\{Gin|}){}$\1\|
|00005030| 35 0a 24 7b 7d 5c 5c 7b | 63 6f 6d 70 61 6e 69 6f |5.${}\\{|companio|
|00005040| 6e 5c 5f 69 6e 5c 5f 48 | 7d 5b 5c 5c 7b 65 69 6e |n\_in\_H|}[\\{ein|
|00005050| 7d 5d 5c 4b 5c 7c 47 5b | 5c 5c 7b 63 6f 6d 70 61 |}]\K\|G[|\\{compa|
|00005060| 6e 69 6f 6e 5c 5f 69 6e | 5c 5f 47 7d 5b 5c 5c 7b |nion\_in|\_G}[\\{|
|00005070| 65 69 6e 7d 5d 5d 3b 7b | 7d 24 5c 32 5c 36 0a 5c |ein}]];{|}$\2\6.\|
|00005080| 34 24 7b 7d 5c 7d 7b 7d | 24 5c 32 5c 37 0a 24 7b |4${}\}{}|$\2\7.${|
|00005090| 7d 5c 26 7b 65 64 67 65 | 5c 5f 61 72 72 61 79 7d |}\&{edge|\_array}|
|000050a0| 5c 6c 61 6e 67 6c 65 5c | 26 7b 65 64 67 65 7d 5c |\langle\|&{edge}\|
|000050b0| 72 61 6e 67 6c 65 7b 7d | 24 20 5c 5c 7b 72 65 76 |rangle{}|$ \\{rev|
|000050c0| 65 72 73 61 6c 7d 28 5c | 7c 48 29 3b 5c 37 0a 24 |ersal}(\||H);\7.$|
|000050d0| 7b 7d 5c 5c 7b 63 6f 6d | 70 75 74 65 5c 5f 63 6f |{}\\{com|pute\_co|
|000050e0| 72 72 65 73 70 6f 6e 64 | 65 6e 63 65 7d 28 5c 7c |rrespond|ence}(\||
|000050f0| 48 2c 5c 33 39 5c 5c 7b | 72 65 76 65 72 73 61 6c |H,\39\\{|reversal|
|00005100| 7d 29 7b 7d 24 3b 5c 70 | 61 72 0a 5c 55 38 2e 5c |}){}$;\p|ar.\U8.\|
|00005110| 66 69 0a 0a 5c 4e 7b 31 | 7d 7b 31 33 7d 54 68 65 |fi..\N{1|}{13}The|
|00005120| 20 50 6c 61 6e 61 72 69 | 74 79 20 54 65 73 74 2e | Planari|ty Test.|
|00005130| 0a 0a 57 65 20 61 72 65 | 20 6e 6f 77 20 72 65 61 |..We are| now rea|
|00005140| 64 79 20 66 6f 72 20 74 | 68 65 20 70 6c 61 6e 61 |dy for t|he plana|
|00005150| 72 69 74 79 20 74 65 73 | 74 20 70 72 6f 70 65 72 |rity tes|t proper|
|00005160| 2e 20 57 65 20 66 6f 6c | 6c 6f 77 0a 5c 63 69 74 |. We fol|low.\cit|
|00005170| 65 5b 70 61 67 65 20 39 | 35 5d 7b 4d 65 3a 62 6f |e[page 9|5]{Me:bo|
|00005180| 6f 6b 7d 2e 20 57 65 20 | 66 69 72 73 74 20 63 6f |ok}. We |first co|
|00005190| 6d 70 75 74 65 20 5c 50 | 42 7b 5c 5c 7b 64 66 73 |mpute \P|B{\\{dfs|
|000051a0| 6e 75 6d 62 65 72 7d 7d | 73 20 61 6e 64 20 5c 50 |number}}|s and \P|
|000051b0| 42 7b 25 0a 5c 5c 7b 70 | 61 72 65 6e 74 7d 7d 73 |B{%.\\{p|arent}}s|
|000051c0| 2c 20 77 65 0a 64 65 6c | 65 74 65 20 61 6c 6c 20 |, we.del|ete all |
|000051d0| 66 6f 72 77 61 72 64 20 | 65 64 67 65 73 20 61 6e |forward |edges an|
|000051e0| 64 20 61 6c 6c 20 72 65 | 76 65 72 73 61 6c 73 20 |d all re|versals |
|000051f0| 6f 66 20 74 72 65 65 20 | 65 64 67 65 73 2c 20 61 |of tree |edges, a|
|00005200| 6e 64 20 77 65 0a 72 65 | 6f 72 64 65 72 20 74 68 |nd we.re|order th|
|00005210| 65 20 61 64 6a 61 63 65 | 6e 79 20 6c 69 73 74 73 |e adjace|ny lists|
|00005220| 20 61 73 20 64 65 73 63 | 72 69 62 65 64 20 69 6e | as desc|ribed in|
|00005230| 20 5c 63 69 74 65 5b 70 | 61 67 65 20 31 30 31 5d | \cite[p|age 101]|
|00005240| 7b 4d 65 3a 62 6f 6f 6b | 7d 2e 0a 57 65 20 74 68 |{Me:book|}..We th|
|00005250| 65 6e 20 74 65 73 74 20 | 74 68 65 20 73 74 72 6f |en test |the stro|
|00005260| 6e 67 20 70 6c 61 6e 61 | 72 69 74 79 2e 0a 54 68 |ng plana|rity..Th|
|00005270| 65 20 61 72 72 61 79 20 | 5c 50 42 7b 5c 5c 7b 61 |e array |\PB{\\{a|
|00005280| 6c 70 68 61 7d 7d 20 69 | 73 20 6e 65 65 64 65 64 |lpha}} i|s needed|
|00005290| 20 66 6f 72 20 74 68 65 | 20 65 6d 62 65 64 64 69 | for the| embeddi|
|000052a0| 6e 67 20 70 72 6f 63 65 | 73 73 2e 20 49 74 0a 72 |ng proce|ss. It.r|
|000052b0| 65 63 6f 72 64 73 20 74 | 68 65 20 70 6c 61 63 65 |ecords t|he place|
|000052c0| 6d 65 6e 74 20 6f 66 20 | 74 68 65 20 73 75 62 73 |ment of |the subs|
|000052d0| 65 67 6d 65 6e 74 73 2e | 0a 0a 0a 0a 5c 59 5c 42 |egments.|....\Y\B|
|000052e0| 5c 34 5c 58 31 33 3a 74 | 65 73 74 20 70 6c 61 6e |\4\X13:t|est plan|
|000052f0| 61 72 69 74 79 5c 58 24 | 7b 7d 5c 45 7b 7d 24 5c |arity\X$|{}\E{}$\|
|00005300| 36 0a 24 5c 26 7b 6e 6f | 64 65 5c 5f 61 72 72 61 |6.$\&{no|de\_arra|
|00005310| 79 7d 5c 6c 61 6e 67 6c | 65 5c 26 7b 69 6e 74 7d |y}\langl|e\&{int}|
|00005320| 5c 72 61 6e 67 6c 65 7b | 7d 24 20 5c 5c 7b 64 66 |\rangle{|}$ \\{df|
|00005330| 73 6e 75 6d 7d 28 5c 7c | 47 29 3b 5c 36 0a 24 7b |snum}(\||G);\6.${|
|00005340| 7d 5c 26 7b 6e 6f 64 65 | 5c 5f 61 72 72 61 79 7d |}\&{node|\_array}|
|00005350| 5c 6c 61 6e 67 6c 65 5c | 26 7b 6e 6f 64 65 7d 5c |\langle\|&{node}\|
|00005360| 72 61 6e 67 6c 65 7b 7d | 24 20 24 7b 7d 5c 5c 7b |rangle{}|$ ${}\\{|
|00005370| 70 61 72 65 6e 74 7d 28 | 5c 7c 47 2c 5c 33 39 5c |parent}(|\|G,\39\|
|00005380| 5c 7b 6e 69 6c 7d 29 3b | 7b 7d 24 5c 37 0a 24 7b |\{nil});|{}$\7.${|
|00005390| 7d 5c 5c 7b 72 65 6f 72 | 64 65 72 7d 28 5c 7c 47 |}\\{reor|der}(\|G|
|000053a0| 2c 5c 33 39 5c 5c 7b 64 | 66 73 6e 75 6d 7d 2c 5c |,\39\\{d|fsnum},\|
|000053b0| 33 39 5c 5c 7b 70 61 72 | 65 6e 74 7d 29 3b 7b 7d |39\\{par|ent});{}|
|000053c0| 24 5c 37 0a 24 7b 7d 5c | 26 7b 65 64 67 65 5c 5f |$\7.${}\|&{edge\_|
|000053d0| 61 72 72 61 79 7d 5c 6c | 61 6e 67 6c 65 5c 26 7b |array}\l|angle\&{|
|000053e0| 69 6e 74 7d 5c 72 61 6e | 67 6c 65 7b 7d 24 20 24 |int}\ran|gle{}$ $|
|000053f0| 7b 7d 5c 5c 7b 61 6c 70 | 68 61 7d 28 5c 7c 47 2c |{}\\{alp|ha}(\|G,|
|00005400| 5c 33 39 5c 54 7b 30 7d | 29 3b 7b 7d 24 5c 37 0a |\39\T{0}|);{}$\7.|
|00005410| 24 7b 7d 5c 7b 7b 7d 24 | 5c 31 5c 36 0a 24 7b 7d |${}\{{}$|\1\6.${}|
|00005420| 5c 26 7b 6c 69 73 74 7d | 5c 6c 61 6e 67 6c 65 5c |\&{list}|\langle\|
|00005430| 26 7b 69 6e 74 7d 5c 72 | 61 6e 67 6c 65 7b 7d 24 |&{int}\r|angle{}$|
|00005440| 20 5c 5c 7b 41 74 74 7d | 3b 5c 37 0a 24 7b 7d 5c | \\{Att}|;\7.${}\|
|00005450| 5c 7b 61 6c 70 68 61 7d | 5b 5c 7c 47 2e 5c 5c 7b |\{alpha}|[\|G.\\{|
|00005460| 66 69 72 73 74 5c 5f 61 | 64 6a 5c 5f 65 64 67 65 |first\_a|dj\_edge|
|00005470| 7d 28 5c 7c 47 2e 5c 5c | 7b 66 69 72 73 74 5c 5f |}(\|G.\\|{first\_|
|00005480| 6e 6f 64 65 7d 28 5c 2c | 29 29 5d 5c 4b 5c 5c 7b |node}(\,|))]\K\\{|
|00005490| 6c 65 66 74 7d 3b 7b 7d | 24 5c 36 0a 5c 26 7b 69 |left};{}|$\6.\&{i|
|000054a0| 66 7d 20 24 7b 7d 28 5c | 52 5c 5c 7b 73 74 72 6f |f} ${}(\|R\\{stro|
|000054b0| 6e 67 6c 79 5c 5f 70 6c | 61 6e 61 72 7d 28 5c 7c |ngly\_pl|anar}(\||
|000054c0| 47 2e 5c 5c 7b 66 69 72 | 73 74 5c 5f 61 64 6a 5c |G.\\{fir|st\_adj\|
|000054d0| 5f 65 64 67 65 7d 28 5c | 7c 47 2e 5c 5c 7b 66 69 |_edge}(\||G.\\{fi|
|000054e0| 72 73 74 5c 5f 6e 6f 64 | 65 7d 28 25 0a 5c 2c 29 |rst\_nod|e}(%.\,)|
|000054f0| 29 2c 5c 33 39 5c 7c 47 | 2c 5c 33 39 5c 5c 7b 41 |),\39\|G|,\39\\{A|
|00005500| 74 74 7d 2c 5c 33 39 5c | 5c 7b 61 6c 70 68 61 7d |tt},\39\|\{alpha}|
|00005510| 2c 5c 33 39 5c 5c 7b 64 | 66 73 6e 75 6d 7d 2c 5c |,\39\\{d|fsnum},\|
|00005520| 33 39 5c 5c 7b 70 61 72 | 65 6e 74 7d 29 29 7b 7d |39\\{par|ent})){}|
|00005530| 24 5c 31 5c 35 0a 5c 26 | 7b 72 65 74 75 72 6e 7d |$\1\5.\&|{return}|
|00005540| 20 5c 5c 7b 66 61 6c 73 | 65 7d 3b 5c 32 5c 36 0a | \\{fals|e};\2\6.|
|00005550| 5c 34 24 7b 7d 5c 7d 7b | 7d 24 5c 32 5c 70 61 72 |\4${}\}{|}$\2\par|
|00005560| 0a 5c 55 35 2e 5c 66 69 | 0a 0a 5c 4d 7b 31 34 7d |.\U5.\fi|..\M{14}|
|00005570| 57 65 20 6e 65 65 64 20 | 74 77 6f 20 67 6c 6f 62 |We need |two glob|
|00005580| 61 6c 20 63 6f 6e 73 74 | 61 6e 74 73 20 5c 50 42 |al const|ants \PB|
|00005590| 7b 5c 5c 7b 6c 65 66 74 | 7d 7d 20 61 6e 64 20 5c |{\\{left|}} and \|
|000055a0| 50 42 7b 5c 5c 7b 72 69 | 67 68 74 7d 7d 2e 0a 0a |PB{\\{ri|ght}}...|
|000055b0| 5c 59 5c 42 5c 34 5c 58 | 31 31 3a 74 79 70 65 64 |\Y\B\4\X|11:typed|
|000055c0| 65 66 73 2c 20 67 6c 6f | 62 61 6c 20 76 61 72 69 |efs, glo|bal vari|
|000055d0| 61 62 6c 65 73 20 61 6e | 64 20 63 6c 61 73 73 20 |ables an|d class |
|000055e0| 64 65 63 6c 61 72 61 74 | 69 6f 6e 73 5c 58 24 7b |declarat|ions\X${|
|000055f0| 7d 5c 6d 61 74 68 72 65 | 6c 2b 5c 45 7b 7d 24 25 |}\mathre|l+\E{}$%|
|00005600| 0a 5c 36 0a 5c 26 7b 63 | 6f 6e 73 74 7d 20 5c 26 |.\6.\&{c|onst} \&|
|00005610| 7b 69 6e 74 7d 20 5c 5c | 7b 6c 65 66 74 7d 24 7b |{int} \\|{left}${|
|00005620| 7d 5c 4b 5c 54 7b 31 7d | 3b 7b 7d 24 5c 36 0a 5c |}\K\T{1}|;{}$\6.\|
|00005630| 26 7b 63 6f 6e 73 74 7d | 20 5c 26 7b 69 6e 74 7d |&{const}| \&{int}|
|00005640| 20 5c 5c 7b 72 69 67 68 | 74 7d 24 7b 7d 5c 4b 5c | \\{righ|t}${}\K\|
|00005650| 54 7b 32 7d 7b 7d 24 3b | 5c 70 61 72 0a 5c 66 69 |T{2}{}$;|\par.\fi|
|00005660| 0a 0a 5c 4d 7b 31 35 7d | 57 65 20 67 69 76 65 20 |..\M{15}|We give |
|00005670| 74 68 65 20 64 65 74 61 | 69 6c 73 20 6f 66 20 74 |the deta|ils of t|
|00005680| 68 65 20 70 72 6f 63 65 | 64 75 72 65 20 5c 50 42 |he proce|dure \PB|
|00005690| 7b 5c 5c 7b 72 65 6f 72 | 64 65 72 7d 7d 2e 20 49 |{\\{reor|der}}. I|
|000056a0| 74 20 66 69 72 73 74 20 | 70 65 72 66 6f 72 6d 73 |t first |performs|
|000056b0| 0a 44 46 53 0a 74 6f 20 | 63 6f 6d 70 75 74 65 20 |.DFS.to |compute |
|000056c0| 5c 50 42 7b 5c 5c 7b 64 | 66 73 6e 75 6d 7d 7d 2c |\PB{\\{d|fsnum}},|
|000056d0| 20 5c 50 42 7b 5c 5c 7b | 70 61 72 65 6e 74 7d 7d | \PB{\\{|parent}}|
|000056e0| 2c 20 5c 50 42 7b 5c 5c | 7b 6c 6f 77 70 74 31 7d |, \PB{\\|{lowpt1}|
|000056f0| 7d 20 61 6e 64 20 5c 50 | 42 7b 25 0a 5c 5c 7b 6c |} and \P|B{%.\\{l|
|00005700| 6f 77 70 74 32 7d 7d 2c | 20 61 6e 64 20 74 68 65 |owpt2}},| and the|
|00005710| 20 6c 69 73 74 20 5c 50 | 42 7b 5c 5c 7b 44 65 6c | list \P|B{\\{Del|
|00005720| 7d 7d 0a 6f 66 20 61 6c | 6c 20 66 6f 72 77 61 72 |}}.of al|l forwar|
|00005730| 64 20 65 64 67 65 73 20 | 61 6e 64 20 61 6c 6c 20 |d edges |and all |
|00005740| 72 65 76 65 72 73 61 6c | 73 20 6f 66 20 74 72 65 |reversal|s of tre|
|00005750| 65 20 65 64 67 65 73 2e | 0a 49 74 20 74 68 65 6e |e edges.|.It then|
|00005760| 20 64 65 6c 65 74 65 73 | 20 74 68 65 20 65 64 67 | deletes| the edg|
|00005770| 65 73 20 69 6e 20 5c 50 | 42 7b 5c 5c 7b 44 65 6c |es in \P|B{\\{Del|
|00005780| 7d 7d 20 61 6e 64 20 66 | 69 6e 61 6c 6c 79 20 69 |}} and f|inally i|
|00005790| 74 0a 72 65 6f 72 64 65 | 72 73 20 74 68 65 20 65 |t.reorde|rs the e|
|000057a0| 64 67 65 73 2e 0a 0a 5c | 59 5c 42 5c 34 5c 58 39 |dges...\|Y\B\4\X9|
|000057b0| 3a 61 75 78 69 6c 69 61 | 72 79 20 66 75 6e 63 74 |:auxilia|ry funct|
|000057c0| 69 6f 6e 73 5c 58 24 7b | 7d 5c 6d 61 74 68 72 65 |ions\X${|}\mathre|
|000057d0| 6c 2b 5c 45 7b 7d 24 5c | 36 0a 5c 26 7b 76 6f 69 |l+\E{}$\|6.\&{voi|
|000057e0| 64 7d 20 5c 5c 7b 72 65 | 6f 72 64 65 72 7d 28 5c |d} \\{re|order}(\|
|000057f0| 26 7b 67 72 61 70 68 7d | 20 24 7b 7d 7b 5c 41 4e |&{graph}| ${}{\AN|
|00005800| 44 7d 5c 7c 47 2c 5c 33 | 39 5c 26 7b 6e 6f 64 65 |D}\|G,\3|9\&{node|
|00005810| 5c 5f 61 72 72 61 79 7d | 5c 6c 61 6e 67 6c 65 5c |\_array}|\langle\|
|00005820| 26 7b 69 6e 74 7d 25 0a | 5c 72 61 6e 67 6c 65 7b |&{int}%.|\rangle{|
|00005830| 7d 24 20 24 7b 7d 7b 5c | 41 4e 44 7d 5c 5c 7b 64 |}$ ${}{\|AND}\\{d|
|00005840| 66 73 6e 75 6d 7d 2c 5c | 33 39 5c 26 7b 6e 6f 64 |fsnum},\|39\&{nod|
|00005850| 65 5c 5f 61 72 72 61 79 | 7d 5c 6c 61 6e 67 6c 65 |e\_array|}\langle|
|00005860| 5c 26 7b 6e 6f 64 65 7d | 5c 72 61 6e 67 6c 65 7b |\&{node}|\rangle{|
|00005870| 7d 24 20 24 7b 7d 7b 25 | 0a 5c 41 4e 44 7d 5c 5c |}$ ${}{%|.\AND}\\|
|00005880| 7b 70 61 72 65 6e 74 7d | 29 7b 7d 24 5c 31 5c 31 |{parent}|){}$\1\1|
|00005890| 5c 32 5c 32 5c 36 0a 24 | 7b 7d 5c 7b 7b 7d 24 5c |\2\2\6.$|{}\{{}$\|
|000058a0| 31 5c 36 0a 5c 26 7b 6e | 6f 64 65 7d 20 5c 7c 76 |1\6.\&{n|ode} \|v|
|000058b0| 3b 5c 36 0a 24 7b 7d 5c | 26 7b 6e 6f 64 65 5c 5f |;\6.${}\|&{node\_|
|000058c0| 61 72 72 61 79 7d 5c 6c | 61 6e 67 6c 65 5c 26 7b |array}\l|angle\&{|
|000058d0| 62 6f 6f 6c 7d 5c 72 61 | 6e 67 6c 65 7b 7d 24 20 |bool}\ra|ngle{}$ |
|000058e0| 24 7b 7d 5c 5c 7b 72 65 | 61 63 68 65 64 7d 28 5c |${}\\{re|ached}(\|
|000058f0| 7c 47 2c 5c 33 39 25 0a | 5c 5c 7b 66 61 6c 73 65 ||G,\39%.|\\{false|
|00005900| 7d 29 3b 7b 7d 24 5c 36 | 0a 5c 26 7b 69 6e 74 7d |});{}$\6|.\&{int}|
|00005910| 20 5c 5c 7b 64 66 73 5c | 5f 63 6f 75 6e 74 7d 24 | \\{dfs\|_count}$|
|00005920| 7b 7d 5c 4b 5c 54 7b 30 | 7d 3b 7b 7d 24 5c 36 0a |{}\K\T{0|};{}$\6.|
|00005930| 24 7b 7d 5c 26 7b 6c 69 | 73 74 7d 5c 6c 61 6e 67 |${}\&{li|st}\lang|
|00005940| 6c 65 5c 26 7b 65 64 67 | 65 7d 5c 72 61 6e 67 6c |le\&{edg|e}\rangl|
|00005950| 65 7b 7d 24 20 5c 5c 7b | 44 65 6c 7d 3b 5c 36 0a |e{}$ \\{|Del};\6.|
|00005960| 24 7b 7d 5c 26 7b 6e 6f | 64 65 5c 5f 61 72 72 61 |${}\&{no|de\_arra|
|00005970| 79 7d 5c 6c 61 6e 67 6c | 65 5c 26 7b 69 6e 74 7d |y}\langl|e\&{int}|
|00005980| 5c 72 61 6e 67 6c 65 7b | 7d 24 20 5c 5c 7b 6c 6f |\rangle{|}$ \\{lo|
|00005990| 77 70 74 31 7d 28 5c 7c | 47 29 24 7b 7d 2c 7b 7d |wpt1}(\||G)${},{}|
|000059a0| 24 20 5c 5c 7b 6c 6f 77 | 70 74 32 7d 28 25 0a 5c |$ \\{low|pt2}(%.\|
|000059b0| 7c 47 29 3b 5c 37 0a 24 | 7b 7d 5c 5c 7b 64 66 73 ||G);\7.$|{}\\{dfs|
|000059c0| 5c 5f 69 6e 5c 5f 72 65 | 6f 72 64 65 72 7d 28 5c |\_in\_re|order}(\|
|000059d0| 5c 7b 44 65 6c 7d 2c 5c | 33 39 5c 7c 47 2e 5c 5c |\{Del},\|39\|G.\\|
|000059e0| 7b 66 69 72 73 74 5c 5f | 6e 6f 64 65 7d 28 5c 2c |{first\_|node}(\,|
|000059f0| 29 2c 5c 33 39 5c 5c 7b | 64 66 73 5c 5f 63 6f 75 |),\39\\{|dfs\_cou|
|00005a00| 6e 74 7d 2c 25 0a 5c 33 | 39 5c 5c 7b 72 65 61 63 |nt},%.\3|9\\{reac|
|00005a10| 68 65 64 7d 2c 5c 33 39 | 5c 5c 7b 64 66 73 6e 75 |hed},\39|\\{dfsnu|
|00005a20| 6d 7d 2c 5c 33 39 5c 5c | 7b 6c 6f 77 70 74 31 7d |m},\39\\|{lowpt1}|
|00005a30| 2c 5c 33 39 5c 5c 7b 6c | 6f 77 70 74 32 7d 2c 5c |,\39\\{l|owpt2},\|
|00005a40| 33 39 5c 5c 7b 70 61 72 | 65 6e 74 7d 29 7b 7d 24 |39\\{par|ent}){}$|
|00005a50| 3b 5c 43 7b 0a 72 65 6d | 6f 76 65 20 66 6f 72 77 |;\C{.rem|ove forw|
|00005a60| 61 72 64 20 61 6e 64 20 | 72 65 76 65 72 73 61 6c |ard and |reversal|
|00005a70| 73 20 6f 66 20 74 72 65 | 65 20 65 64 67 65 73 20 |s of tre|e edges |
|00005a80| 7d 5c 37 0a 5c 26 7b 65 | 64 67 65 7d 20 5c 7c 65 |}\7.\&{e|dge} \|e|
|00005a90| 3b 5c 37 0a 5c 26 7b 66 | 6f 72 61 6c 6c 7d 20 24 |;\7.\&{f|orall} $|
|00005aa0| 7b 7d 28 5c 7c 65 2c 5c | 33 39 5c 5c 7b 44 65 6c |{}(\|e,\|39\\{Del|
|00005ab0| 7d 29 7b 7d 24 5c 31 5c | 35 0a 24 7b 7d 5c 7c 47 |}){}$\1\|5.${}\|G|
|00005ac0| 2e 5c 5c 7b 64 65 6c 5c | 5f 65 64 67 65 7d 28 5c |.\\{del\|_edge}(\|
|00005ad0| 7c 65 29 7b 7d 24 3b 5c | 43 7b 20 77 65 20 6e 6f ||e){}$;\|C{ we no|
|00005ae0| 77 20 72 65 6f 72 64 65 | 72 20 61 64 6a 61 63 65 |w reorde|r adjace|
|00005af0| 6e 63 79 20 6c 69 73 74 | 73 20 61 73 20 64 65 73 |ncy list|s as des|
|00005b00| 63 72 69 62 65 64 20 69 | 6e 0a 5c 63 69 74 65 5b |cribed i|n.\cite[|
|00005b10| 70 61 67 65 20 31 30 31 | 5d 7b 4d 65 3a 62 6f 6f |page 101|]{Me:boo|
|00005b20| 6b 7d 20 7d 5c 32 5c 37 | 0a 5c 26 7b 6e 6f 64 65 |k} }\2\7|.\&{node|
|00005b30| 7d 20 5c 7c 77 3b 5c 36 | 0a 24 7b 7d 5c 26 7b 65 |} \|w;\6|.${}\&{e|
|00005b40| 64 67 65 5c 5f 61 72 72 | 61 79 7d 5c 6c 61 6e 67 |dge\_arr|ay}\lang|
|00005b50| 6c 65 5c 26 7b 69 6e 74 | 7d 5c 72 61 6e 67 6c 65 |le\&{int|}\rangle|
|00005b60| 7b 7d 24 20 5c 5c 7b 63 | 6f 73 74 7d 28 5c 7c 47 |{}$ \\{c|ost}(\|G|
|00005b70| 29 3b 5c 37 0a 5c 26 7b | 66 6f 72 61 6c 6c 5c 5f |);\7.\&{|forall\_|
|00005b80| 65 64 67 65 73 7d 20 24 | 7b 7d 28 5c 7c 65 2c 5c |edges} $|{}(\|e,\|
|00005b90| 33 39 5c 7c 47 29 7b 7d | 24 5c 35 0a 24 7b 7d 5c |39\|G){}|$\5.${}\|
|00005ba0| 7b 7b 7d 24 5c 31 5c 36 | 0a 24 7b 7d 5c 7c 76 5c |{{}$\1\6|.${}\|v\|
|00005bb0| 4b 5c 5c 7b 73 6f 75 72 | 63 65 7d 28 5c 7c 65 29 |K\\{sour|ce}(\|e)|
|00005bc0| 3b 7b 7d 24 5c 36 0a 24 | 7b 7d 5c 7c 77 5c 4b 5c |;{}$\6.$|{}\|w\K\|
|00005bd0| 5c 7b 74 61 72 67 65 74 | 7d 28 5c 7c 65 29 3b 7b |\{target|}(\|e);{|
|00005be0| 7d 24 5c 36 0a 24 7b 7d | 5c 5c 7b 63 6f 73 74 7d |}$\6.${}|\\{cost}|
|00005bf0| 5b 5c 7c 65 5d 5c 4b 28 | 28 5c 5c 7b 64 66 73 6e |[\|e]\K(|(\\{dfsn|
|00005c00| 75 6d 7d 5b 5c 7c 77 5d | 3c 5c 5c 7b 64 66 73 6e |um}[\|w]|<\\{dfsn|
|00005c10| 75 6d 7d 5b 5c 7c 76 5d | 29 5c 3f 5c 54 7b 32 7d |um}[\|v]|)\?\T{2}|
|00005c20| 2a 5c 5c 7b 64 66 73 6e | 75 6d 7d 5b 5c 7c 77 5d |*\\{dfsn|um}[\|w]|
|00005c30| 3a 28 28 25 0a 5c 5c 7b | 6c 6f 77 70 74 32 7d 5b |:((%.\\{|lowpt2}[|
|00005c40| 5c 7c 77 5d 5c 47 5c 5c | 7b 64 66 73 6e 75 6d 7d |\|w]\G\\|{dfsnum}|
|00005c50| 5b 5c 7c 76 5d 29 5c 3f | 5c 54 7b 32 7d 2a 5c 5c |[\|v])\?|\T{2}*\\|
|00005c60| 7b 6c 6f 77 70 74 31 7d | 5b 5c 7c 77 5d 3a 5c 54 |{lowpt1}|[\|w]:\T|
|00005c70| 7b 32 7d 2a 5c 5c 7b 6c | 6f 77 70 74 31 7d 5b 5c |{2}*\\{l|owpt1}[\|
|00005c80| 7c 77 5d 2b 25 0a 5c 54 | 7b 31 7d 29 29 3b 7b 7d ||w]+%.\T|{1}));{}|
|00005c90| 24 5c 36 0a 5c 34 24 7b | 7d 5c 7d 7b 7d 24 5c 32 |$\6.\4${|}\}{}$\2|
|00005ca0| 5c 36 0a 24 7b 7d 5c 7c | 47 2e 5c 5c 7b 73 6f 72 |\6.${}\||G.\\{sor|
|00005cb0| 74 5c 5f 65 64 67 65 73 | 7d 28 5c 5c 7b 63 6f 73 |t\_edges|}(\\{cos|
|00005cc0| 74 7d 29 3b 7b 7d 24 5c | 36 0a 5c 34 24 7b 7d 5c |t});{}$\|6.\4${}\|
|00005cd0| 7d 7b 7d 24 5c 32 5c 70 | 61 72 0a 5c 66 69 0a 0a |}{}$\2\p|ar.\fi..|
|00005ce0| 5c 4d 7b 31 36 7d 57 65 | 20 73 74 69 6c 6c 20 68 |\M{16}We| still h|
|00005cf0| 61 76 65 20 74 6f 20 67 | 69 76 65 20 74 68 65 20 |ave to g|ive the |
|00005d00| 70 72 6f 63 65 64 75 72 | 65 20 5c 50 42 7b 5c 5c |procedur|e \PB{\\|
|00005d10| 7b 64 66 73 5c 5f 69 6e | 5c 5f 72 65 6f 72 64 65 |{dfs\_in|\_reorde|
|00005d20| 72 7d 7d 2e 20 49 74 27 | 73 20 61 20 62 69 74 0a |r}}. It'|s a bit.|
|00005d30| 6c 6f 6e 67 20 62 75 74 | 20 73 74 61 6e 64 61 72 |long but| standar|
|00005d40| 64 2e 0a 0a 5c 59 5c 42 | 5c 34 5c 58 39 3a 61 75 |d...\Y\B|\4\X9:au|
|00005d50| 78 69 6c 69 61 72 79 20 | 66 75 6e 63 74 69 6f 6e |xiliary |function|
|00005d60| 73 5c 58 24 7b 7d 5c 6d | 61 74 68 72 65 6c 2b 5c |s\X${}\m|athrel+\|
|00005d70| 45 7b 7d 24 5c 36 0a 5c | 26 7b 76 6f 69 64 7d 20 |E{}$\6.\|&{void} |
|00005d80| 5c 5c 7b 64 66 73 5c 5f | 69 6e 5c 5f 72 65 6f 72 |\\{dfs\_|in\_reor|
|00005d90| 64 65 72 7d 24 7b 7d 28 | 5c 26 7b 6c 69 73 74 7d |der}${}(|\&{list}|
|00005da0| 5c 6c 61 6e 67 6c 65 5c | 26 7b 65 64 67 65 7d 5c |\langle\|&{edge}\|
|00005db0| 72 61 6e 67 6c 65 7b 7d | 24 20 24 7b 7d 7b 5c 41 |rangle{}|$ ${}{\A|
|00005dc0| 4e 44 7d 25 0a 5c 5c 7b | 44 65 6c 7d 2c 5c 33 39 |ND}%.\\{|Del},\39|
|00005dd0| 7b 7d 24 5c 26 7b 6e 6f | 64 65 7d 20 5c 7c 76 24 |{}$\&{no|de} \|v$|
|00005de0| 7b 7d 2c 5c 33 39 7b 7d | 24 5c 26 7b 69 6e 74 7d |{},\39{}|$\&{int}|
|00005df0| 20 24 7b 7d 7b 5c 41 4e | 44 7d 5c 5c 7b 64 66 73 | ${}{\AN|D}\\{dfs|
|00005e00| 5c 5f 63 6f 75 6e 74 7d | 2c 5c 33 39 5c 26 7b 6e |\_count}|,\39\&{n|
|00005e10| 6f 64 65 25 0a 5c 5f 61 | 72 72 61 79 7d 5c 6c 61 |ode%.\_a|rray}\la|
|00005e20| 6e 67 6c 65 5c 26 7b 62 | 6f 6f 6c 7d 5c 72 61 6e |ngle\&{b|ool}\ran|
|00005e30| 67 6c 65 7b 7d 24 20 24 | 7b 7d 7b 5c 41 4e 44 7d |gle{}$ $|{}{\AND}|
|00005e40| 5c 5c 7b 72 65 61 63 68 | 65 64 7d 2c 5c 33 7b 2d |\\{reach|ed},\3{-|
|00005e50| 31 7d 5c 33 39 5c 26 7b | 6e 6f 64 65 5c 5f 61 72 |1}\39\&{|node\_ar|
|00005e60| 72 61 79 7d 25 0a 5c 6c | 61 6e 67 6c 65 5c 26 7b |ray}%.\l|angle\&{|
|00005e70| 69 6e 74 7d 5c 72 61 6e | 67 6c 65 7b 7d 24 20 24 |int}\ran|gle{}$ $|
|00005e80| 7b 7d 7b 5c 41 4e 44 7d | 5c 5c 7b 64 66 73 6e 75 |{}{\AND}|\\{dfsnu|
|00005e90| 6d 7d 2c 5c 33 39 5c 26 | 7b 6e 6f 64 65 5c 5f 61 |m},\39\&|{node\_a|
|00005ea0| 72 72 61 79 7d 5c 6c 61 | 6e 67 6c 65 5c 26 7b 69 |rray}\la|ngle\&{i|
|00005eb0| 6e 74 7d 25 0a 5c 72 61 | 6e 67 6c 65 7b 7d 24 20 |nt}%.\ra|ngle{}$ |
|00005ec0| 24 7b 7d 7b 5c 41 4e 44 | 7d 5c 5c 7b 6c 6f 77 70 |${}{\AND|}\\{lowp|
|00005ed0| 74 31 7d 2c 5c 33 39 5c | 26 7b 6e 6f 64 65 5c 5f |t1},\39\|&{node\_|
|00005ee0| 61 72 72 61 79 7d 5c 6c | 61 6e 67 6c 65 5c 26 7b |array}\l|angle\&{|
|00005ef0| 69 6e 74 7d 5c 72 61 6e | 67 6c 65 7b 7d 24 20 24 |int}\ran|gle{}$ $|
|00005f00| 7b 7d 7b 25 0a 5c 41 4e | 44 7d 5c 5c 7b 6c 6f 77 |{}{%.\AN|D}\\{low|
|00005f10| 70 74 32 7d 2c 5c 33 7b | 2d 31 7d 5c 33 39 5c 26 |pt2},\3{|-1}\39\&|
|00005f20| 7b 6e 6f 64 65 5c 5f 61 | 72 72 61 79 7d 5c 6c 61 |{node\_a|rray}\la|
|00005f30| 6e 67 6c 65 5c 26 7b 6e | 6f 64 65 7d 5c 72 61 6e |ngle\&{n|ode}\ran|
|00005f40| 67 6c 65 7b 7d 24 20 24 | 7b 7d 7b 5c 41 4e 44 7d |gle{}$ $|{}{\AND}|
|00005f50| 25 0a 5c 5c 7b 70 61 72 | 65 6e 74 7d 29 7b 7d 24 |%.\\{par|ent}){}$|
|00005f60| 5c 31 5c 31 5c 32 5c 32 | 5c 36 0a 24 7b 7d 5c 7b |\1\1\2\2|\6.${}\{|
|00005f70| 7b 7d 24 5c 31 5c 36 0a | 5c 26 7b 6e 6f 64 65 7d |{}$\1\6.|\&{node}|
|00005f80| 20 5c 7c 77 3b 5c 36 0a | 5c 26 7b 65 64 67 65 7d | \|w;\6.|\&{edge}|
|00005f90| 20 5c 7c 65 3b 5c 37 0a | 24 7b 7d 5c 5c 7b 64 66 | \|e;\7.|${}\\{df|
|00005fa0| 73 6e 75 6d 7d 5b 5c 7c | 76 5d 5c 4b 5c 5c 7b 64 |snum}[\||v]\K\\{d|
|00005fb0| 66 73 5c 5f 63 6f 75 6e | 74 7d 5c 50 50 3b 7b 7d |fs\_coun|t}\PP;{}|
|00005fc0| 24 5c 36 0a 24 7b 7d 5c | 5c 7b 6c 6f 77 70 74 31 |$\6.${}\|\{lowpt1|
|00005fd0| 7d 5b 5c 7c 76 5d 5c 4b | 5c 5c 7b 6c 6f 77 70 74 |}[\|v]\K|\\{lowpt|
|00005fe0| 32 7d 5b 5c 7c 76 5d 5c | 4b 5c 5c 7b 64 66 73 6e |2}[\|v]\|K\\{dfsn|
|00005ff0| 75 6d 7d 5b 5c 7c 76 5d | 3b 7b 7d 24 5c 36 0a 24 |um}[\|v]|;{}$\6.$|
|00006000| 7b 7d 5c 5c 7b 72 65 61 | 63 68 65 64 7d 5b 5c 7c |{}\\{rea|ched}[\||
|00006010| 76 5d 5c 4b 5c 5c 7b 74 | 72 75 65 7d 3b 7b 7d 24 |v]\K\\{t|rue};{}$|
|00006020| 5c 36 0a 5c 26 7b 66 6f | 72 61 6c 6c 5c 5f 61 64 |\6.\&{fo|rall\_ad|
|00006030| 6a 5c 5f 65 64 67 65 73 | 7d 20 24 7b 7d 28 5c 7c |j\_edges|} ${}(\||
|00006040| 65 2c 5c 33 39 5c 7c 76 | 29 7b 7d 24 5c 35 0a 24 |e,\39\|v|){}$\5.$|
|00006050| 7b 7d 5c 7b 7b 7d 24 5c | 31 5c 36 0a 24 7b 7d 5c |{}\{{}$\|1\6.${}\|
|00006060| 7c 77 5c 4b 5c 5c 7b 74 | 61 72 67 65 74 7d 28 5c ||w\K\\{t|arget}(\|
|00006070| 7c 65 29 3b 7b 7d 24 5c | 36 0a 5c 26 7b 69 66 7d ||e);{}$\|6.\&{if}|
|00006080| 20 24 7b 7d 28 5c 52 5c | 5c 7b 72 65 61 63 68 65 | ${}(\R\|\{reache|
|00006090| 64 7d 5b 5c 7c 77 5d 29 | 7b 7d 24 5c 35 0a 24 7b |d}[\|w])|{}$\5.${|
|000060a0| 7d 5c 7b 7b 7d 24 5c 43 | 7b 20 65 20 69 73 20 61 |}\{{}$\C|{ e is a|
|000060b0| 20 74 72 65 65 20 65 64 | 67 65 20 7d 5c 31 5c 36 | tree ed|ge }\1\6|
|000060c0| 0a 24 7b 7d 5c 5c 7b 70 | 61 72 65 6e 74 7d 5b 5c |.${}\\{p|arent}[\|
|000060d0| 7c 77 5d 5c 4b 5c 7c 76 | 3b 7b 7d 24 5c 36 0a 24 ||w]\K\|v|;{}$\6.$|
|000060e0| 7b 7d 5c 5c 7b 64 66 73 | 5c 5f 69 6e 5c 5f 72 65 |{}\\{dfs|\_in\_re|
|000060f0| 6f 72 64 65 72 7d 28 5c | 5c 7b 44 65 6c 7d 2c 5c |order}(\|\{Del},\|
|00006100| 33 39 5c 7c 77 2c 5c 33 | 39 5c 5c 7b 64 66 73 5c |39\|w,\3|9\\{dfs\|
|00006110| 5f 63 6f 75 6e 74 7d 2c | 5c 33 39 5c 5c 7b 72 65 |_count},|\39\\{re|
|00006120| 61 63 68 65 64 7d 2c 5c | 33 39 25 0a 5c 5c 7b 64 |ached},\|39%.\\{d|
|00006130| 66 73 6e 75 6d 7d 2c 5c | 33 39 5c 5c 7b 6c 6f 77 |fsnum},\|39\\{low|
|00006140| 70 74 31 7d 2c 5c 33 39 | 5c 5c 7b 6c 6f 77 70 74 |pt1},\39|\\{lowpt|
|00006150| 32 7d 2c 5c 33 39 5c 5c | 7b 70 61 72 65 6e 74 7d |2},\39\\|{parent}|
|00006160| 29 3b 7b 7d 24 5c 36 0a | 24 7b 7d 5c 5c 7b 6c 6f |);{}$\6.|${}\\{lo|
|00006170| 77 70 74 31 7d 5b 5c 7c | 76 5d 5c 4b 5c 5c 7b 4d |wpt1}[\||v]\K\\{M|
|00006180| 69 6e 7d 28 5c 5c 7b 6c | 6f 77 70 74 31 7d 5b 5c |in}(\\{l|owpt1}[\|
|00006190| 7c 76 5d 2c 5c 33 39 5c | 5c 7b 6c 6f 77 70 74 31 ||v],\39\|\{lowpt1|
|000061a0| 7d 5b 5c 7c 77 5d 29 3b | 7b 7d 24 5c 36 0a 5c 34 |}[\|w]);|{}$\6.\4|
|000061b0| 24 7b 7d 5c 7d 7b 7d 24 | 5c 53 48 43 7b 65 6e 64 |${}\}{}$|\SHC{end|
|000061c0| 20 74 72 65 65 20 65 64 | 67 65 20 7d 5c 32 5c 36 | tree ed|ge }\2\6|
|000061d0| 0a 5c 26 7b 65 6c 73 65 | 7d 5c 35 0a 24 7b 7d 5c |.\&{else|}\5.${}\|
|000061e0| 7b 7b 7d 24 5c 31 5c 36 | 0a 24 7b 7d 5c 5c 7b 6c |{{}$\1\6|.${}\\{l|
|000061f0| 6f 77 70 74 31 7d 5b 5c | 7c 76 5d 5c 4b 5c 5c 7b |owpt1}[\||v]\K\\{|
|00006200| 4d 69 6e 7d 28 5c 5c 7b | 6c 6f 77 70 74 31 7d 5b |Min}(\\{|lowpt1}[|
|00006210| 5c 7c 76 5d 2c 5c 33 39 | 5c 5c 7b 64 66 73 6e 75 |\|v],\39|\\{dfsnu|
|00006220| 6d 7d 5b 5c 7c 77 5d 29 | 7b 7d 24 3b 5c 53 48 43 |m}[\|w])|{}$;\SHC|
|00006230| 7b 20 6e 6f 0a 65 66 66 | 65 63 74 20 66 6f 72 20 |{ no.eff|ect for |
|00006240| 66 6f 72 77 61 72 64 20 | 65 64 67 65 73 20 7d 5c |forward |edges }\|
|00006250| 36 0a 5c 26 7b 69 66 7d | 20 24 7b 7d 28 28 5c 5c |6.\&{if}| ${}((\\|
|00006260| 7b 64 66 73 6e 75 6d 7d | 5b 5c 7c 77 5d 5c 47 5c |{dfsnum}|[\|w]\G\|
|00006270| 5c 7b 64 66 73 6e 75 6d | 7d 5b 5c 7c 76 5d 29 5c |\{dfsnum|}[\|v])\|
|00006280| 56 5c 7c 77 5c 45 5c 5c | 7b 70 61 72 65 6e 74 7d |V\|w\E\\|{parent}|
|00006290| 5b 5c 7c 76 5d 7b 7d 24 | 29 5c 43 7b 0a 66 6f 72 |[\|v]{}$|)\C{.for|
|000062a0| 77 61 72 64 20 65 64 67 | 65 20 6f 72 20 72 65 76 |ward edg|e or rev|
|000062b0| 65 72 73 61 6c 20 6f 66 | 20 74 72 65 65 20 65 64 |ersal of| tree ed|
|000062c0| 67 65 20 7d 5c 31 5c 36 | 0a 24 7b 7d 5c 5c 7b 44 |ge }\1\6|.${}\\{D|
|000062d0| 65 6c 7d 2e 5c 5c 7b 61 | 70 70 65 6e 64 7d 28 5c |el}.\\{a|ppend}(\|
|000062e0| 7c 65 29 3b 7b 7d 24 5c | 32 5c 36 0a 5c 34 24 7b ||e);{}$\|2\6.\4${|
|000062f0| 7d 5c 7d 7b 7d 24 5c 53 | 48 43 7b 65 6e 64 20 6e |}\}{}$\S|HC{end n|
|00006300| 6f 6e 2d 74 72 65 65 20 | 65 64 67 65 20 7d 5c 32 |on-tree |edge }\2|
|00006310| 5c 36 0a 5c 34 24 7b 7d | 5c 7d 7b 7d 24 5c 53 48 |\6.\4${}|\}{}$\SH|
|00006320| 43 7b 20 65 6e 64 20 66 | 6f 72 61 6c 6c 20 7d 5c |C{ end f|orall }\|
|00006330| 43 7b 20 77 65 20 6b 6e | 6f 77 20 5c 50 42 7b 5c |C{ we kn|ow \PB{\|
|00006340| 5c 7b 6c 6f 77 70 74 31 | 7d 5b 5c 7c 76 5d 7d 20 |\{lowpt1|}[\|v]} |
|00006350| 61 74 20 74 68 69 73 20 | 70 6f 69 6e 74 20 61 6e |at this |point an|
|00006360| 64 0a 6e 6f 77 20 6d 61 | 6b 65 20 61 20 73 65 63 |d.now ma|ke a sec|
|00006370| 6f 6e 64 20 70 61 73 73 | 20 6f 76 65 72 20 61 6c |ond pass| over al|
|00006380| 6c 20 20 20 20 20 20 61 | 64 6a 61 63 65 6e 74 20 |l      a|djacent |
|00006390| 65 64 67 65 73 20 6f 66 | 20 5c 50 42 7b 5c 7c 76 |edges of| \PB{\|v|
|000063a0| 7d 20 74 6f 20 63 6f 6d | 70 75 74 65 20 5c 50 42 |} to com|pute \PB|
|000063b0| 7b 25 0a 5c 5c 7b 6c 6f | 77 70 74 32 7d 7d 20 7d |{%.\\{lo|wpt2}} }|
|000063c0| 5c 32 5c 36 0a 5c 26 7b | 66 6f 72 61 6c 6c 5c 5f |\2\6.\&{|forall\_|
|000063d0| 61 64 6a 5c 5f 65 64 67 | 65 73 7d 20 24 7b 7d 28 |adj\_edg|es} ${}(|
|000063e0| 5c 7c 65 2c 5c 33 39 5c | 7c 76 29 7b 7d 24 5c 35 |\|e,\39\||v){}$\5|
|000063f0| 0a 24 7b 7d 5c 7b 7b 7d | 24 5c 31 5c 36 0a 24 7b |.${}\{{}|$\1\6.${|
+--------+-------------------------+-------------------------+--------+--------+